Problems Deleting Email On A Terminal Server - Exchange 2010, Outlook 2003

When attempting to delete email in the setup below, users received a popup stating "Unknown Error" and could not delete the mail. Selecting the mail and trying to delete again sometimes allowed the deletion to occur.

Users were on a Terminal Server running Windows Server 2003 R2 (SP2) and were using Outlook 2003 (SP3). The Exchange server had recently been migrated to Exchange 2010 (SP1).

The problem was resolved by updating Exchange 2010 to SP3.