I had a user yesterday who could not open her mailbox with Outlook. I checked the mailbox on a terminal server and had the same issue. The strange thing is that I could access the mailbox via Outlook Web Access without any problem, and I also could open her inbox (File-->Open Other User's Folder) with a domain admin account in an Outlook client without issue. I gave up diagnosing the issue and just deleted and recreated her mailbox and this resolved the problem.
Later in the afternoon, I had another report of the same issue with another user. At this point I do not want to just delete and recreate his account, I want to resolve the issue.
I've tried rebooting Exchange.
I've tried disabling and then reconnecting his mailbox.
There aren't any events in the event viewer on Exchange.
I have over 100 other users who are not having any issues.
I'm lost at what to do next.