Getting "Unknown Error" in Outlook 2003/Exchange 2010 when attempting to delete items from Inbox

When opening Outlook 2003 on our Terminal Server, everything comes up fine. We are connected to Exchange 2010 on Server 2008.

The problem occurs when attempting to delete a message from the Inbox. Regardless if you hit the delete key on the keyboard or the delete button on the toolbar, it does nothing the first time. Then, when you try a second time, it WILL delete, but it gives an error that says "Unknown Error".

This has become very annoying. Here is our history on what we've done to correct the problem:

First Attempt: Connected to session and rebuilt users mail profile, however when Outlook launched, all of his e-mail messages were displaying as if it did not recreate the profile. Logged user off of the TS, and back on. Same issue. Removed all mail profiles, launched Outlook and created a new profile. Still getting the Outlook unknown error when user presses delete or uses the X icon to delete messages. Must do this operation twice for the error to display.

Second Attempt: Found that there was a Rollup available.  The server had rollup 4, so this shouldn't be the issue.

Third: Tried exporting mail to pst, then removing mailbox, actually removed account from AD, recreated, imported mail.  same error.

Fourth: Found that items CAN be deleted with Shift-Delete

Any help with this problem would be greatly appreciated.

Thanks!