I'm a huge proponent of SpinVox, a service that converts voicemails to text. Messages are delivered via SMS and/or e-mail. Currently, I've got two mobile numbers and one landline. All three forward busy and unanswered calls to my voicemail number at SpinVox, which means that I can "listen" to my voicemails wherever I am, without making a call. When I'm in areas without GPRS, I set SpinVox to use SMS to deliver messages, but normally, I receive them only as email. My Blackberry's incoming mail filter marks messages from SpinVox as being "Level 1" in priority, which highlights those messages in red and tells the phone to notify me by vibrating and beeping.
When I'm in the country, I still call in to listen to more interesting voicemails. After all, it is still nice to hear someone's voice on the other end. SpinVox makes message retrieval easy by providing a short code for each message -- you just call up, type in the code, and your message is read back to you. It also functions in the traditional manner, with queued messages played back in reverse chronological order.
SpinVox also offers a whole bunch of services similar to those that Jott provides, but I haven't tried any of them out. It's priced a bit high, but so is making voicemail calls from out of the country.
I think that if I only traveled to areas with good data infrastructure, I'd stick with GrandCentral, which features voicemail played through a web interface. But for me, text is better than audio.