The following is what I wrote for getting SMS off the phone. I edited it for voicemail. I assure you that this all works, since I personally checked to see that I had a voicemail on my PC awhile back when I was writing this up.
Anyway, here's what you can use for a PC (for a Mac you can use the extractor, but you'll have to work off the backup on your Mac, see this
link for the Mac version ):
http://www.reincubate.com/labs/iphon...ackup-windows/
Use the iPhone Backup Extractor to make a db file of the voicemail (or any number of other parts in the backup....notes, etc., you'll want to check the option "restore some or all files from backup manually.")
http://menoob.com/2008/12/04/how-to-...your-computer/
You don't necessarily need DiskAid if you already have the backup on your PC, but DiskAid is invaluable if you've somehow crapped your computer and only have the iPhone, since it can read the iPhone and get your backup on to a computer. After extracting the part of the backup you want, use the linked SQLite Database Browser to then make a wav file (I think that was the type of file, or it's some other sound extension) of each of the voicemails. You'll be able to at least see your voicemail (or any number of other parts in the backup....notes, etc., that you extracted from the backup above).
Sorry, if the above sounds obtuse, but if you have problems I'll post later tonight when I'm at home and have access to these programs and can better layout the steps if you get confused.