I have a constant voicemail logo in my notifications bar, but I have no voicemails waiting, I have tried battery pulling but it doesn't seem too do anything :s
Go to messages, View Folder, Visual Voicemail to double check if any are there. Also while you are there hit menu, search by, advanced, scroll down to Show and choose unread only, then menu and search