I’m using Outlook 2013 to connect to my Office 356 account. DNS is set up correctly, with autodiscover.mydomain.com pointing to autodiscover.outlook.com. I recently had to re-create my account and it took 20+ minutes to find the Office 365 server.
I right-clicked on the Outlook icon in the system tray and choose Test E-mail AutoConfiguration…. There I could see that it was trying the HttpsRootDomain (https://mydomain.com) about ten times (at almost two minutes each), each time with a 12002 result:
Eventually it registers HttpsRootDomain as a failure and moves on to the HttpsAutoDiscoverDomain (https://autodiscover.mydomain.com). Once it got that, it quickly resolved to Office 365. Tests from https://testconnectivity.microsoft.com worked much faster, only trying the HttpsRootDomain once.
The workaround is to add a registry key to tell autodiscover to skip the HttpsRootDomain:
[HKEY_CURRENT_USER\Software\Microsoft\Office\15.0\Outlook\AutoDiscover]
"ExcludeHttpsRootDomain"=dword:00000001
With that in place, autodiscovery takes under ten seconds:
It’s expected that https://mcbsys.com fails. It’s not expected, and so far unexplained, why Outlook is trying so many times before giving up and moving on to https://autodiscover.mcbsys.com.
Update November 19, 2015
Microsoft support has confirmed that this bug was introduced in the June 2015 update to Outlook. Besides the registry key above, another workaround is to roll back to the May 2013 update version 15.0.4719.1002. Instructions for that can be found in KB article 2770432.