I have a TMO Curve, every time I power it off and back on, the VM icon appears in the display. I called TMO and they said they fixed it from their side but it keeps happening. I've had 2 Curves and both have done this. Has anyone else had this happen?

You don't have sms blocked in your firewall, do you? Options >Security Options >Firewall. Not sure if that will block the voicemail notifications or not, though.

Also, have you tried calling your voicemail again? Have you tried removing the battery?

Wirelessly posted (Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.0) BlackBerry8320/4.2.2 Profile/MIDP-2.0 Configuration/CLDC-1.1 VendorID/100)

I have the same issue. It does not happen everytime I reset my phone but it does happen often. I simply call voicemail and the second I connect to voicemail the icon goes away.