In case you run into slow account setup with the newly released Outlook 2016 version, which can take up to 10 mins or more, here’s a possible fix. Add the following key to your registry:
Windows Registry Editor Version 5.00
This is caused by some bug (or leftover debug code) that forces Outlook to try a little too hard to obtain a response from the Autodiscover directory on your root domain. If the domain resolves in DNS but does not respond to HTTP queries (i.e. you don’t have an actual server to acknowledge them), this will cause timeout error, and Outlook will try again and again and again. Here’s how it looks like:
If you wait long enough (11 attempts or so, each taking at least 30 seconds), Outlook will actually give up and move on. But if you don’t like waiting, the reg key above will force Outlook to bypass this particular check and it will continue to the next method. So as a result the process will take a substantially smaller amount of time.
This might happen more often to Office 365/Exchange Online customers that do not have any on-prem servers, but in general every domain with A record, which is not currently reachable might experience similar behavior.