Solution:

 

1. Enable Encryption in the Outlook 2003 Profile.

image

2. Create a GPO to enable Encryption for Outlook 2003 clients.

http://support.microsoft.com/kb/2006508

 

3. Disable the Encryption requirement on the Exchange 2010 server.

From PowerShell on the Exchange server: Set-RpcClientAccess -Server:ExchangeServerName -EncryptionRequired:$False