No jailbreaking or re-recording required!
This does require some familiarity with the command prompt (aka. command shell).
I was thinking of writing a small program or script to automate this but I am not sure what language to write it in.
I also don't really know how to illustrate this.
Step 1: When you sync your iPhone, iTunes backs up your files
Mac: ~/Library/Application Support/MobileSync/Backup/
Windows XP: \Documents and Settings\(username)\Application Data\Apple Computer\MobileSync\Backup\
Windows Vista and Windows 7: \Users\(username)\AppData\Roaming\Apple Computer\MobileSync\Backup\
Apple has some more information about iPhone and iTouch backups here.
It doesn't mention voicemail, but voicemail files are indeed included.
Step 2: You could just read these files, but iTunes renames them
First, be sure to make a copy of the entire directory and work only on the copy.
From a command prompt, you can use the command file, which reads a file and figures out what sort of data it actually contains. Then you can rename the file with the proper extension so your operating system will recognize it and can open it. For example, voicemail is stored as an Adaptive Multi-Rate Codec (GSM telephony) .amr file. If you rename a file with this extension, Quicktime will open it.
The Macintosh command prompt includes the file command as part of the operating system.
On Windows, you have to download and install the file command manually. This program is one possibility using the windows command prompt.
Another possibility is cygwin which installs a unix-like command shell that includes the file command (This is what I used, since I already had it installed).
Once you have the command installed you would type something like:
to see what sort of file each mddata file actually is.
Here is some of the results from my iPhone:
f879f904659340b84f23853b997e0a13b8db608f.mddata: Adaptive Multi-Rate Codec (GSM telephony)
f8d2d53f86ac550432e597654a2b5d456524a5ca.mddata: Apple binary property list
f936b60c64de096db559922b70a23faa8db75dbd.mddata: SQLite 3.x database
fb3108570150f89af665302ff4d3c25027c149b9.mddata: PNG image data, 127 x 127, 16-bit/color RGB, non-interlaced
fb5933a1d7f0155d2656a00f4ed5e6c63429262a.mddata: JPEG image data, JFIF standard 1.01
fb7786ced1add24313fa258c8e1ed041e24d52a4.mddata: Apple binary property list
fc5e3306c70847e0c7eff69da7a33a2ec978e516.mddata: JPEG image data, EXIF standard 2.21
fdff09f7f56b266b40c42606bc71a06fac258007.mddata: ASCII text
Quicktime will open the following files:
change extension to .amr: Adaptive Multi-Rate Codec (GSM telephony)
change extension to .jpeg: JPEG image data, EXIF standard 2.21
change extension to .png: PNG image data, 127 x 127, 16-bit/color RGB, non-interlaced
change extension to .mpeg: ISO Media, MPEG v4 system, iTunes AAC-LC
change extension to .mpeg: ISO Media, Apple QuickTime movie
sqlite browser will open SQLite 3.x database files.
.mdinfo files and some of the .mddata files are Apple binary property list. This page talks about how to read them. Here is some source code. Or use this program.
Step 3: Caveats
You can have iTunes encrypt your backups, and this method won't work.
I found iBackupBot (Backup Manager Software for iTunes) software ($34.95 trialware) which makes browsing iTunes backups much easier, but won't let me listen to voicemail or save it to another file.
I also tried YouMail which completely redirects your voicemail to a different service (that includes being able to email and transcript voicemail) but it was way overkill for what I wanted.
Google Voice looks like it will email and transcript voicemail as well. You need to get and invite to use this service, however.