1. Possible priv.edb problems
2. Possible edb.log problems
3. Using Server side Antivirus Application against ESE store
4. Using Client side Antivirus application against Outlook
1 & 2 are determined by using ISINTEG and ESEUTIL, but the server must taken offline (after hours job and may be extensive depending on size of edb)
3 & 4 are easy enough, if present disable temporarily and see if the condition improves
Check event viewer for any application errors that occur while user is trying to accomplish this.
If you are not using any AV application than 1 & 2 are probable. Anytime a message is written, modified, deleted from the mail account this write is first done to the EDB.LOG files and memory and then when time permitts the PRIV.EDB. So its logical that this user's mailbox or location within the EDB database maybe corrupt or have problems. ISINTEG will help find any table errors while ESEUTIL will help determine the integrity of the database as a whole.
Be carefull with these tools and don't just use any switch unless you know what its intended for, you can cause more harm then good.