I use phonetag, essentially you forward your voicemail over to them and then everytime someone leaves one, their system transcribes it into text and either emails or txt messages it back to your phone (and even other email addresses/phones). So there is no more "checking" voicemail... the contents of your messages are all onscreen.
http://www.phonetag.com/
I'm on the pay-per-VM plan since I don't get many. It's 35cents/message.
-j