There is an issue with some previous Outlook cumulative updates that will cause some clients to fail Autodiscover lookups.
Essentially what is happening is that the Outlook client uses the user principal name (UPN) instead of the Primary SMTP address for the lookup. If the UPN and SMTP address are different, Autodiscover will fail.
For instance, let’s say my primary SMTP address was email@example.com and the account that I logged in with (my UPN) was firstname.lastname@example.org. When I start up Outlook with a new profile and it queried my Exchange 2007 or Exchange 2010 server Autodiscover service, it should automatically create my profile for me. But if you have installed the Outlook 2010 Cumulative Update released October 26, 2010 or the Outlook 2007 Cumulative Update released January 11, 2011 then this is probably not working as intended. This also includes any cumulative updates that may have been released after them up to the fixes below.
This is fixed in the most recent cumulative updates for Outlook 2007 and Outlook 2010.
For Outlook 2010:
The fix is in the most recent Outlook 2010 Cumulative Update (February Update):
From that KB:
“The automatic profile configuration process that uses the Autodiscover service does not complete successfully in Outlook 2010 after you apply the hotfix package that is described in KB article 2405793.
Note The automatic profile configuration process uses the user principal name (UPN) instead of the primary SMTP address. Specifically, this issue occurs when the UPN differs from the primary SMTP address.”
For Outlook 2007:
The fix is in the most recent Outlook 2007 Cumulative Update (February Update):
From that KB:
”Consider the following scenario:
Your user principle name (UPN) differs from your SMTP address in Office Outlook 2007.
You install the hotfix package that is described in Knowledge Base article 2412171.
You use the Autodiscover service.
In this scenario, the Autodiscover service fails.”
Hopefully that is helpful. If you have any further questions please ask your PFE or TAM.