Russel is dead on! Whenever you have a problem like this, it will be due to a corrupt mailbox. Exporting to a pst and creating a new mailbox is the best solution. You could attempt a fix using the isinteg:
isinteg -test alltests -pri -fix
to see if it will fix the corruption. DO NOT use the eseutil to fix this problem. A hard repair using the eseutil is a solution of LAST RESORT. To run the isinteg you must stop the Information Store service. To export to a pst, you need only run Exmerge (found on your Exchange CD), which you do with the store running. Perform a two-step merge, not a one-step.
After exporting the mailbox contents, compare the size of the pst to the user's mailbox size (right-click on Outlook Today - Mailbox - user name, and select Properties, then mailbox size). The two numbers should be fairly close, but do not have to match. Once you are sure you got a good export, delete the mailbox.
When you create the new mailbox, you can use the same name as the original mailbox on the General tab of the mailbox properties, but switch to the Advanced tab and alter the Directory Name by adding a digit to the end. This can ONLY be done while creating the mailbox! Once you have closed the properties page, the Directory Name CANNOT BE CHANGED!
This will prevent any corruption associated with the original Directory Name from affecting the new mailbox - trust me, I've seen it happen!
Send a test message to the new mailbox before importing the pst contents into it. Otherwise, nothing will be imported, as Exmerge will not populate an empty mailbox (unless MS has fixed it).
Good luck,
Bob