You said you created a new profile check for this setting on the clients that are having issues using Outlook 2003. This is the first thing I would check for to see if this is enable.
Outlook 2003
To manually update an existing Outlook 2003 profile so that it uses RPC encryption with Exchange 2010, follow these steps:
1.In Control Panel, open the Mail item.
2.Click Show Profiles.
3.Select your profile, and then click Properties.
4.Click E-mail Accounts.
5.Select View or change existing e-mail accounts, and then click Next.
6.Select the Microsoft Exchange Server account, and then click Change.
7.In the dialog box that contains your mailbox server and user name, click More Settings.
8.In the Microsoft Exchange Server dialog box, click the Security tab.
9.Click to select the Encrypt data between Microsoft Office Outlook and Microsoft Exchange Server check box, and then click OK.
http://support.microsoft.com/kb/2006508