Saving voicemails to MP3 format

I have a number of messages in my cell phone voice mail that I’d like to save to MP3 format and keep for a long time. The people from Verizon (who, in order for this OP to not devolve into a pit rant, I shall otherwise leave out of this) and who have these stored on their server, cannot apparently do this for me.

So, how can I get these saved away from Verizon?

Can I use Skype, call my VM with my computer, listen to these messages and simultaneously save them to the HD? if so, how?

Yep, the easiest is probably with Skype. Use their call recording feature. It’s in the options. You’ll need to go in later with an audio editor (like Audacity) to chop the recording up into separate files (if that’s what you want).

You can also do this with phone software if you use a Treo.