I'm with T-Mobile in the UK and voicemail calls don't come out of my monthly inclusive calls allowance so I would have to pay for every message I listen to.
I've scanned through this thread and haven't spotted a mention of Hullomail (https://market.android.com/details?id=com.hullomail.messaging.android
), it completely replaces your carrier's voicemail and you can access messages by calling a regular landline number (I assume that there are numbers for different countries but haven't checked) which comes out of my allowance, using their app with my data allowance or using the web interface from a PC. In addition it will optionally email all voicemails to you in mp3 format and, if you don't mind ads in the app (messages are unaffected) then its free.
I know not all carriers allow you to redirect your voicemail to it but it's worth checking out in case it fits your needs. I especially like the fact that the app shows who the messages are from and I can play any of them in any order (the app shows which are read/unread).