A customer contacted to report a problem with Outlook's AutoDiscover feature. The customer was a former BPOS customer that was testing some mailboxes deployed onto a new on-premises environment. The testExchangeConnectivity validation tool was reporting consistent results, so it appeared to be client related, but given the general complexity of the environment (domains, networks, VPNs, etc.), we felt it necessary to first rule out the server as an issue. The connectivity checker for Outlook was running the Autodiscover test and returning the following results on the log tab.
Local autodiscover for myserver.gov failed (0x8004010F)
Redirect check to http://myserver.gov/autodiscover/autodiscover.xml starting
Svr Record Lookup for http://myserver.gov/autodiscover/autodiscover.xml failed (0x80004005)
Initially, we focused on the 0x80004005 event and traced it to a problem with the IIS environment. A quick look at the IIS logs and client-side packet capture both showed a 301 (permanently removed) response from the web server. This didn't make much sense as Exchange is configured for a 302 redirect. After ruling out network connectivity issues, network load balancer issues and a few client side configurations, we found some data in the registry at the key HKEY_CURRENT_USER\Software\Microsoft\Office\12.0\Outlook\AutoDiscover (or 14.0 if you're using Outlook 2010). These values existed on the BPOS client machine but did not exist on mine.
We set the values to zero and Outlook began behaving normally again. These values are installed and used in a variety of ways by customers of the Exchange Online service. The final resolution/cause appeared to be that the registry settings installed by BPOS prevented Outlook from using the HTTPS AutoDiscover service to get its configuration information.