So nach weiteren Stunden der Lösungssuche, habe ich das Problem im Griff bekommen.
Kleine Ursache, Große Wirkung!
Ich habe ja geschrieben, das ich in einer Testumgebung arbeite und damit auch keine Internetverbindung habe. Am DHCP Server war natürlich noch die Gateway Adresse des Routers der vorherigen SBS 2011 Umgebung eingetragen.
Nur das der Router in der Testumgebung gar nicht existiert und die Gateway Adresse gar nicht erreichbar ist. Und genau das ist wohl das Problem.
Wenn das Gateway am Client leer ist, kenne ich den Fehler, dass Outlook mit der Meldung aussteigt "kein Gateway an der Netzwerkkarte eingetragen" - aber das war mir neu. Gut normal habe ich in einer Testumgebung ja auch Internet geschaltet bzw eine funktionierendes Gateway. Hier musste ich nur sicher gehen, das die Anlage nicht Online geht!
Kurzer Hand habe ich die Gateway Adresse auf die IP des AD Server eingestellt, habe natürlich immer noch kein Internet, aber jetzt läuft Outlook sauber durch und bekomme die Fehlermeldung nicht mehr.
silviov's post in Exchange 2016 Migration - Outlook Verbindungsproblem wurde als beste Lösung markiert.