I’ve found a lot of Outlook to Exchange server connection problems can be fixed (and speeded up) by editing this registry key:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Exchange\Exchange Provider

And making sure ncacn_ip_tcp is first on the list.