I sound like a broken record on this. And anyone reading some of my previous posts on the subject might think I'm spamming for this company. I'm not. Anyhow....
For an absolutely amazing and free visual voice mail experience - check out YouMail. Google it. There's an app in market also. Free. Great notification settings. All sorts of cool stuff. I'm just trying to spread the word on this company. No one knows about it and YouMail is just flat out awesome.
Seriously, sorry for sounding spammy. I just really like this app. I hear so many problems about vm and YouMail just works.