So I rebuilt my Surface Pro 3 and was struggling to connect back to the corporate on premise Exchange Server which is 2010. After a bit of research it turns out Outlook 2016 is trying to use Exchange Active Sync (EAS) to connect which Exchange 2010 and the two are not happy together.
I came across this article that gave a good overview of the issues as EAS works fine for mobile/tabley sync and Mail app as they support EAS.
So to make it work (I think), I added the following registry entry and then autodiscover finally worked, however it took a good few minutes to connect and resolve. Just be paitient.
If your Exchange Server does not have MAPI over HTTP enabled, you’ll need to set a registry key to disable MAPI over HTTP. This will cause Outlook 2016 to fall back to RPC over HTTP.
Happy Outlooking now.