Never had the problem associated with voicemail but if you are talking about a message showing up for missed calls in Messaging. This was driving me nuts for awhile until I got some help at Crackberry.

1. Go into phone mode as if you are about to dial a number.
2. Go to options ---> call logging --> none
3. That should take care of the problem.