Hi
Just a guess, but did you try to move the mailbox to a fresh database within exchange. Over time, Exchange DBs tend to get more and more inconsistencies depending on what is being done on exchange or especially if the DBs grow a lot.
Are you familiar with i.e. Eseutil? Here's a nice article to it:
Exchange Server Database Utility Guide
The downside of this is that you have to take the store in question down - the workaround is the above mentioned method of moving mailboxes to fresh stores/storage groups.