Update von meiner Seite. Ich habe (viel zu lange) an der falschen Stelle gesucht.
Nachdem ich mich mehr in Richtung NTLM Fehler orientiert habe, habe ich anhand der Fehlermeldungen am Exchange NTLM Fehlercodes gesehen und bin letztendlich über die GPO
"Network security: Restrict NTLM: NTLM authentication in this domain" gestoßen. Möglicherweise war die zu Testzwecken (irgendwann mal) kurzzeitig aktiv.
Setze ich die GPO auf disabled und mache ein gpupdate, dann klappt wieder alles.
Was ich noch nicht 100% verstehe, nehme ich die Policy wieder weg, dann klappt es wieder nicht mehr. Ich hätte jetzt noch keinen Grund gefunden, warum NTLM wieder gesperrt ist, wenn ich die Policy wegnehme.
Update: Noch ein Update, warum es ohne Policy auch nicht mehr funktioniert hat, da auf einem Domaincontroller (Master) ein RegKey gesetzt war, der anscheinend bei dem o.a. Test nicht richtig gestellt wurde:
Computer\HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Netlogon\Parameters
RestrictNTLMInDomain war auf 7 (deny all), Standard ist 0
