Da meine Testumgebung kein Internet hat aber (jetzt kommts) Outlook beim Start im Standard den im PC eingestelletn Gateway anpingt bzw. beim fehlschlagen des Ping Outlook nicht mit dem Exchange verbindet kam nie eine Verbindung bei mir zustande.
Bis Outlook 2013 kann man das mit dem folgenden Registry Eintrag lösen solte man noch RPCoHTTPS (beim Mapi siehe Outlook 2016 Erklärung) benutzen.
Bei Outllok 2016 (mit MAPIoHTTPS) gibt es den Schalter nicht mehr aber da es sich nur um einen Ping Test handelt kann man dann in den Gatewayeinstellungen eine beliebig pingbare IP eintragen. Im Anschluss startet Outlook wir gewohnt und verbindet sich auch ganz normal.
Was der Sinn dieser Einstellung (Gatewaycheck beim Outlookstart) soll habe ich noch nicht nachlesen können wenn es überhaupt einen Sinn dafür gibt.