Haven't had this happen on my Tilt, but did on my last phone on Sprint (not sim card related). I ended up having to leave myself a new voice mail, then call in and listen to it and delete it.
Also, I found on Sprint that if I deleted a message and hung up before the icon cleared, it sometimes stayed on. Doesn't happen on my Tilt on AT&T, but I mention it in case it affects someone else.
ROM version 1.57.502.2
Rom Date 08/25/07