Well, there's probably a better way, but I can't think of it, so here is what I know works:
Get the cheapest phone you can find. Tear apart the handset and find the wires running to the speaker. Clip the wires and attach a mono mini jack plug in place of the speaker. Plug this mini jack into the line-in (or microphone input) on your computer's soundcard, and plug the phone into the wall. Dial into the voicemail system (probably easiest to use another phone on the same line for this) and use your favorite recording software to record the voicemails as they play.
Ok, so this is lacking in elegance to the point that I'm embarrassed to post it, but if you want to go to the trouble, it will work.
Cheers,
Warden