OS: MacOS Mavericks
iPhone 5s

Voicemail messages are stored in the backup, and saved as one file per message. Nice. Backups are stored in:

~/Library/Application\ Support/MobileSync/Backup

Within the Backup directory, there directories of backups for all your iDevices. I made it easy on myself by performing a backup just prior to saving the my voicemails.

Launch Terminal.

Go to the backup directory:

$ cd ~/Library/Application\ Support/MobileSync/Backup

List the files/directories and sort by date:

$ ls -trl

The last directory, in my case, was the one with the most recent backup I had just completed.

Make a copy of this directory to mess around with:

$ cp -rp 44e1c7c3d719bd24e3b9dd1aa87eb924c9153ff5 /Users/jgz/TestBackup

Change directories to the where you made your copy:

In my case:

$ cd /Users/jgz/TestBackup

Then, identify the voicemail files using the file command:

$ file * | grep “Adaptive Multi-Rate Codec”

This will list all of the voice mail messages in the backed up.

Rename the files with an .amr file extension, and play them in QuickTime. Once, you find the ones you want to keep, export them as Audio only files (m4a) to keep.