This was solved.
The reason why this was happening is because we use a self-signed certificate for our Exchange 2007 internal communication. These certs were not installed as Trusted Authorities by our test clients, but they were on our Outlook 2010 clients.