Whenever my phone reboots, or I get a new voicemail message, the notification bar and the vv app will show (for example) 5 new messages, but 4 of those are old messages that I have already listened to. Back when I had listened to them, they moved from the New tab to the All tab, and they were normal font, not bold anymore.

Could it be that a message is marked as "read" only when you've played it to the the very end. There's no way to mark a message as read (long press popup menu or menu button).

Thanks!