A great article from Strangely Dim on how to backup voicemail messages from the iPhone simply, with no additional apps, and no Jailbreaking.
1) Backup your phone in iTunes
2) Run a simple Terminal script (copy and paste)
3) Wait a few seconds and all of your voicemails are converted to .amr files. The one trick is giving the script a minute or so to run, I kept running it over and over without waiting for it to terminate on its own. Patience!
The script you need to run is here:
pushd ~/Library/Application\ Support/MobileSync/Backup ; \
for I in `find . -name *.mddata -exec grep -la “#\!AMR” {} +` ; \
do cp $I $OLDPWD/`basename -s mddata $I`amr ; \
done ; \
popd
And make sure to click through to Eric’s original article. Thanks for the hint!