I have deleted all my voice mail.
I have deleted all my SMS messages
I have restarted my phone 3 times.
I have called myself and left 3 short messages and deleted them.
I have called myself and left a 15 second message, and listened to the message and deleted it.
How do I get that notification to go away?
If I go to SETTINGS, then click CALL, I can see the Clear Voice Mail notification, but it it not lite up and not clickable. I click on it and no Joy.
I finally fixed it myself, just a lucky guess.
Turn the phone off.
Remove the back cover.
Remove the battery.
Wait 10 sec. (It is a soft reset)
Put the battery back
Put the back cover back
Turn the phone on.
Weird but everyone of my voicemails from today came back as new.
I listened to them from the notification bar and deleted them all.
Best luck to you all.
Not totally related, but you might consider getting Google Voice to replace your normal voicemail. You still get visual voicemail, but you get to also keep all your voicemails forever instead of them always auto-deleting after 30 days. You can also check your voicemail from a computer, if either your phone isn't working, or you're someplace where calling voicemail would use precious minutes (like another country).
I upgraded to new HTC EVO Sprint with Andriod 2.2 and after searching a lot of places did not get an answer to this issue but I did trouble shoot and resolve it. Basically, the phone comes with Voicemail to Text app (trail version) which shows up on the home page. It keeps prompting you to setup the voicemail on a new phone. When you do it, the it has a pending voicemail in the app. Now, that is the cause of the voicemail notification on top left corner of your EVO. Even if you play that message and hear it multiple times, the notification does not go away. Just delete the damn message on that app and restart the phone. Now your voicemail icon should not appear when you do not have a voicemail.
Steps to Clear Voicemail Notification on a new Sprint HTC EVO when you have no voicemail:
1. Open Voicemail app on home page
2. Play the 'pending' message
3. Delete the message
4. Restart your phone (Turn off and Turn on)
5. You are done. Voicemail notification cleared and now continue enjoying your life with one less irritation.