Trots att man gör alla inställningar korrekt i DNS servrarna, både internt och externt så kommer autodiscover att krångla när man innan kört en intern Exchange server.
Detta beror på någonting som heter SCP (Service Connection Point) och som finns i Active Directory. Lösningen på problemet är att stänga av SCP på den interna miljön.

Detta gör man enklast via Powershell på Exchange servern med detta kommando: Set-ClientAccessServer -Identity “SERVERNAME” -AutoDiscoverServiceInternalUri $NULL

Mer information finns här: http://www.agileit.com/news/outlook-profile-autodiscover-service-order-of-precedence-and-disabling-scp-for-hosted-exchangeoffice-365-migrations/
Och här: http://theucguy.net/service-connection-point-scp-in/

Har man inte kontroll över Active Directory / Exchange miljön så kan man även konfigurera varje klient manuellt. Detta med hjälp av en XML fil och lite registernycklar. Lättast att göra detta är via ett gratisprogram som heter MessageOps Config 365. Man kan tanka hem programmet här: http://www.messageops.com/software/office-365-tools-and-utilities/config-365/

Tänk på att om du väljer att krysa i rutan Prefer Local XML – for autodiscover så måste du rensa registernycklarna efter att man löst de interna problemen med SCP.
Annars kan det sluta fungera om Microsoft byter namn på Office 365 servrarna.
Registernycklar som skall tas bort:

Outlook 2007:
HKEY_CURRENT_USER\Software\Microsoft\Office\12.0\Outlook\AutoDiscover

Outlook 2010:
HKEY_CURRENT_USER\Software\Microsoft\Office\14.0\Outlook\AutoDiscover
ExcludeHttpRedirect=0
ExcludeHttpsAutodiscoverDomain=1
ExcludeHttpsRootDomain=1
ExcludeScpLookup=1
ExcludeSrvRecord=1
PreferLocalXML=1