I must say this problem is all too familiar. I am experiencing a similar issue, and have no solution yet.
The problem is that users can not see the messages in their inbox. When emails arrive (the folder indicated new emails arriving and the number keeps going up) they just don't appear in the inbox. All filters are off and views are correct. Autoarchive is not an issue either. Additionally, the sent mail, and deleted mail folders also contain "invisible" emails.
I'm on MS 5.5 and have three users. One user has no problem, the other two have this same problem.
When we change the delivery to a personal folder, the emails are visible in the personal inbox folder. When we copy the inbox/deleted/sent mail to a personal folder, we can see all emails correctly. When we sync the inbox with a PPC, the emails are visible in the PPC outlook.
Everything seems to be working fine, except we can't see the emails in those folders. We also use public folders that all users can see fine.
This problem occurred after we performed Office Updates.