W/o the actual error message it's fairly difficult to give an accurate diagnosis, but I'm going to invoke some psychic powers and see if I can come up with something useful for you.
I've had a couple of situations where fairly old Exchange 2003 installations had Outlook 2010 introduced and the users of Outlook 2010 reported problems sending messages. The root cause was that the named property quota had been reached on the Exchange 2003 server and Outlook 2010, requiring the ability to create some named properties, was failing in a very non-graceful manner.
Review the Application Event Log on the Exchange Server computer and look for event id 9667 from the source "MSExchangeIS". This error will show the details of the named property that Outlook 2010 is attempting to create.
You should do a couple of things:
You should install the hotfix described in this article and set the appropriate registry settings to prevent exhaustion of the named property quota with "promoted" Internet X-headers again.
Follow the steps outlined in this article to increase the named property quota.
This will permit Outlook 2010 to create the named properties it needs to function properly and will prevent future exhaustion of the named property quota by Internet X-headers being "promoted" into named properties.
You can read some good background about this the Exchange Team blog.
(As an aside, both Blackberry Enterprise Server and Microsoft's own ActiveSync also fail in non-graceful ways when not permitted to create named properties subsequent to their installation.)