Recently I started using Google Voice. I'm very happy with this service. The biggest thing that has helped me is the fact the phone can download the voicemails over WiFi. (I have no cell service where I work). Not to mention being able to setup Google voice to forward to another phone if you don't answer your mobile. Simply awesome.
Also, the voice transcripts are nice, not perfect, but you can figure out what the message is saying without having to listen to the Vmail, good if you're in a meeting or something.
I got tired of waiting on an invite from google, and just bought an invite on eBay, $2 and it has been the best $2 on an app I've spent so far.