Interesting topic you bring up.
So I was playing with the voicemail options from my Verizon Storm.
I was trying to not get a stupid msg in my msg box every damn time I got a voicemail because I can see the Icon on the top of the screen,(I hate redundancy). You call up your voicemail and go to personal options by pressing '4' and you can turn your "Voicemail Waiting Indicator" on or off. When I turned it 'OFF' there was the icon, even when I had zero messages in my voice mailbox. Just call it up and turn it back on, hopefully it works for you.
If anyone can tell me how to change my options to not get anything in my msg box that would be great. I already set my Call Logging to Log NONE of the calls. Thanks in Advance.