Perhaps you can try to take out the sim card after powering down. Wait a min or 2 and reinsert SIM then power on. If that doesn't work, sounds like it is another of the widespread issues and bugs in 5.0, unless you haven't updated to 5.0 yet. On a related note, but different phone, I had a similar issue and called my VM and slowly went through option 7 to delete messages just to make sure. I also had to have a data connection, for some reason, for the icon to disappear.
Try calling your number from al landline or someone else's cell phone, and leave yourself a voicemail. Then listen to it, delete it, and see if the "phantom" message also goes away.