So I was traveling outside the country recently and making any phone call using my cellphone (including checking my voicemail) is .69 cents per minute! I looked around for a solution and finally found a kinda cool service called GotVoice. This company will retrieve your voicemails from your cell phone 3 times a day and make them available to you as MP3s with an email notification when new messages arrive.
The basic service is free, and they *do* try to upsell you to a premium service with more features, but the basic service will check your voicemail three times a day automatically and more times if you do it manually via their website.
It's worked flawlessly for me so far. Anyone else using a similar service?