Call your cell from another line and leave a VM. Then check the VM with your cell and delete the message (usually 7 on the keypad), then exit the VM system with #.
That should resend the "clear VM icon" signal from your carrier.
I should have asked which message did you erase. The audio one or the phone message in your meassage folder. My answer was to get rid of the phone icon on the screen after a call is left, not the tape icon, sorry. If you go back in and delete the audio message like the above post said, the tape should go away. On my 8900 I can delete with 7 after the message or 77 during the message. And * exits the mailbox, although I hit the hang-up key instead. I guess there could be a problem with the phone.