Exchange-Postfach lässt sich auf einem PC nicht einbinden

Moin,

wir haben kürzlich bei einem Kunden sämtliche PCs ausgetauscht.
Da mussten wir dann natürlich auf jedem PC Outlook neukonfigurieren.

Es gibt bei dem Kunden 3 PCs, die das gleiche Postfach nutzen (Die angemeldeten User selbst haben kein Postfach).
Das hat bei zwei PCs wunderbar funktioniert, bei dem dritten PC hat dies allerdings nicht geklappt.
Credentials wurden zwar angenommen und Outlook war angeblich auch vollständig konfiguriert,
aber beim Starten des Outlooks kam die Meldung, dass der Server nicht erreichbar sei.

Habe zwei unserer Test-Accounts testweise dann unter dem gleichen User eingerichtet: Keine Probleme beim Öffnen von Outlook.

Habe das Profil gelöscht, Daten unter Localappdata und Appdata Roaming gelöscht und neu eingerichtet, gleicher Fehler wieder.

Auch auf dem Exchange 2013 habe ich keine Fehler in der Ereignisanzeige bekommen, zumal es auf den anderen beiden PCs funktioniert.
Auch mit die drei alten PCs konnten ohne Probleme auf das eine Postfach zugreifen.

Irgendwelche Ideen woran es liegen könnte?

Viele Grüße