Actually, scratch that. It will now properly calculate their true total whenever they login.
I'm not sure if that will help you solve the actual problem.
I have found that if a user who sent you a PM is deleted, the USER_ID of that sender is changed to 1 in the table 'PRIVATE_MESSAGE_POSTS' but not in the table 'PRIVATE_MESSAGE_TOPICS'. And that's why you will see the PM-envelope flashing but that PM will not turn up in your list, so you cannot read it.
I have created a solution for our forums and added a button 'Mark All Read' to the 'viewmessages' page.
Then in delete.inc.php I will set the 'MESSAGE_LAST_READ' for all PM's
AND also update 'PRIVATE_MESSAGE_TOPICS' and set the 'USER_ID' to 1 in case the actual listed user_id doesn't exist. And voila, the PM-list now shows the "missing" PM too.
Off course only the second step would be actually required to correct the problem.
