The PM indicator is all based off date and an entry in the database. It sounds like something is definitely out of sync somewhere since you have a variety of different reports.
What I'd do for now is just mark everything as read for everyone, post a note that you're doing this so everyone realizes what's happening, and then see if it starts working properly. You can do that with the following query:
update ubbt_PRIVATE_MESSAGE_USERS set MESSAGE_LAST_READ='1203201245'
