It turned out that all I had to do was call AT&T and have them deactivate my voicemail account. Of course getting AT&T to understand that I wanted to deactivate not activate the account want quite as easy. As soon as they deactivated my voicemail account the icon went away. My Googlevoice account voicemail still works fine. My first clue that the AT&T voicemail account might be the cause of the problem was when I changed back to the carrier voicemail from Google voice and closed this setting in the Settings menu, I got the message "No Change", which clued me in that the problem may be because of AT&T.
1- Clear Data for the Phone's application. Once cleared, the notification disappears.
2- Call your mobile number from another phone and leave a voicemail.
3- From your phone, call your voicemail to check the message. The notification should show up again.
4- Delete the voice message. The notification should disappear.
5- Restart your phone.
I have an htc evo 3d and none of the solutions in this form worked but after trying to solve this for two months I stumbled on to the solution, for the htc evo 3d any way. I hold the power button down until the power options screen appears than I select restart (Green Button) below the button it says Close all apps and restart phone. After the phone restarted it took a few seconds for all the icones to return to normal and Viola! no more annoying voice mail notification. Hope this helps.
I have a Motorola Droid LG and after several tries of advice other than clearing data...that one did not appeal to me at all....I saw a good answer and it worked. Call yourself, leave message. When you get that, listen and then clear and the "ghost" icon was gone too. That simple!!! Thanks to whoever left that simple answer and hope it helps someone else ✌