So.Was lange währt wird endlich gut.
Wir haben es geschafft (mit externer Unterstützung)
Nachdem bei uns auf den Rechner die Firewall (Sophos UTM9) als Proxy eingetragen ist, deswegen auch auf den lokalen Rechner das Zertifikat exchange.unsere-domain.de, gehen die Rechner den Weg durchs Netzwerk, Über die Firewall/Proxy, sind somit eigentlich "außerhalb" des Netzwerkes und greifen dann wieder auf den internen Exchange zu.
Obwohl in dem Zertifikat auch exchange.unsere-domäne.local drin steht UND S02.unsere-domäne.local (S02 = Exchange) UND auch in den Netzwerkeinstellungen eingetragen ist, das der Proxy für lokale Adressen umgangen werden soll, hat das alles nicht funktioniert.
Nach langem Suchen haben wir dann entdeckt, das in der Firewall das Zertifikat für Zugriffe von extern auch nochmal eingetragen war.
Zertifikat ausgetauscht und alles gut...