Had this problem with my TP1, and I have my Sprint voicemail disabled because it interferes with my virtual office VM.
Here's what you have to do:
1) Get to Advanced technical support (the regular techs can't help you)
2) Turn off your phone
3) Have them clear out your voicemail account
4) Reboot phone
I've found that I usually have to walk them through the steps, because they try to take shortcuts (which don't work). They must do each of these things in order, or the VM notification will come back. Also, the VM notification disappears instantly if they did it correctly - don't let them tell you it takes up to 60 minutes - it doesn't. You may have to be persistent, because like I said earlier, the techs sometimes don't follow the exact steps even if you ask them to.
If (like me) you have Sprint VM disabled, but got a VM notification for some reason, there are a few extra steps involved:
1) Get to Advanced technical support (the regular techs can't help you)
2) Turn off your phone
3) Have them re-enable your VM service
4) Have them clear out your voicemail account
5) Have them disable your VM service
6) Reboot phone
Again, they must follow the steps in order, or it won't work.