I don't know why, but sometimes after I restart my phone, I have a VM indicator on when I don't have any voicemail. I simply leave myself a voicemail and delete. The icon goes away afterwards.
haha funny. I actually got it. I just got a brand new SIM from tmobile and now I dont get VM when I reboot. I dont get VM when I return from airplane mode either. SUPER!