I have been switching between AT&T SIM and T-Mobile SIM for the past few dayson my P800. AT&T supports notifying you with the little tape player icon when you get a voicemail.
On T-Mobile however, you get an SMS.
After switching with the T-Mobile SIM, the tape player stays there even though I don't have any voicemail. I also made sure I deleted all voicemail when I was using the AT&T SIM.
FYI, if I do a master reset, the icon is gone but as soon as I restore, the icon shows up again.