Outlook 2010 verbindet sich nicht sauber mit Exchange 2013

Hallo in die Runde,

eine nicht ganz seltene Frage, aber bis dato hab keine Lösung für das Problem gefunden. Das Szenario um das es geht:

Wir betreiben einen Exchange Server 2013 (Name: MX01) (aktueller Patchstand)
sowie 4 Terminalserver auf Windows Server 2012 R2 (Name: RDS01,RDS02,RDS03,RDS04) (ebenfalls aktueller Patchstand)

Über das Wochenende haben wir zwei neue WTS aufgesetzt (Name: RDS05, RDS06), eigentlich soweit alles normal ohne Zwischenfälle.
Jeder WTS hat Office 2010 Standard installiert.

Einen der zwei neuen WTS in die RDS-Farm mit aufgenommen.

Nun zum Problem:

Setzen wir einen bestehenden User von einem alten Terminalserver (Windows Server 2012) um, erhalten wir bei der Erstkonfiguration durch Outlook ständig das Anmeldeprompt. Farmuser, die bereits auf der Farm die ganze Zeit gearbeitet haben und über den Sessionbroker auf den RDS05 geschoben werden, arbeiten auch ganz normal in Outlook ohne Problem.
Meldet sich einer der User vom alten TS auf der Farm auf einer der anderen 4 WTS (RDS01-04) an, kann er sein Outlook ganz normal einrichten.

Innerhalb der GPO sehe ich keine Außergewöhnlichkeiten, wenn sind auch alle WTS mit den selben Rechten ausgestattet.

Ein Test auf dem zweiten neuen WTS (RDS06) bringt aber das selbe Ergebnis, sprich irgendetwas scheint in der Konfiguration am WTS nicht zu passen, ich komm nur nicht drauf was es sein könnte.

Bisher probiert:

-Zertifikat vom Mailserver (MX01) als vertrauenswürdig in das Computerkonto eingebunden
-Reparaturinstallation auf Office
-Drehen der Anmeldeinformationen als Domain\User (in diesem Fall kann er sich dann verbinden, aber nicht durch die automatische Installation)
-Neustart des WTS

Hat noch wer eine Idee, was es sein könnte?

Grüße
Forseti

Screenshot1:

Bis zu diesem Schritt verläuft alles normal.

Screenshot2:

Hier tritt der Fehler dann auf, bei regulärem Autodiscover sollte er das einfach so durchführen ohne abzufragen.