I originally had issues with the YouMail developed visual voicemail app but since have upgraded to the .16 beta and it downloads great. I also learned based on the marketing site at Visual Voicemail Plus
that maybe it would auto-update my new messages if I turned on text message alerts. So I tested it out. Low and behold, I ran a few tests and the instant a new message is left, YouMail fires off a text message and bam, a new voicemail is displayed in the app and is immediately green (which means you can listen online or offline to the message). I am not a big text messager so now in one fell swoop I have new voicemail alerts in the form of an icon on my banner for text messages, that indicate I should go directly to my YouMail app and see who might be trying to reach me and listen to what they have to say (or if you pay for transcripting, read what they might have to say).
All that said, make sure you enable some sort of text plan, I have 400 text messages and if I get that many voicemails in a month I might freak out on someone anyway. Give it a shot and you may find that you are a convert as well just like I am.