Zertifkat wird manchmal nicht vertraut

Hallo !

Ich habe hier eine hybride Exchange Konfiguration. Die normalen User Mailboxen sind aber bereits alle zu Exchange Online migriert.
99% der User starten Outlook ohne Zertifikats Abfragen und alles ist in Ordnung.

Ich habe aber genau 5 Geräte, die bei jedem Outlook Start einen Sicherheitshinweis werfen und die User dem Cert trauen müssen. Als Error kommt:

"Das Sicherheitszertifikat wurde von einer Firma ausgestellt, die Sie nicht als vertrauenswürdig eingestuft haben". Die beiden anderen Häkchen sind okay.

Wenn ich in das Zertifikat am Client reinschaue steht dort

"Ausgestellt für meinedomain.mail.onmicrosoft.com"
und
"Ausgestellt von Meine Firma Proxy CA".

Der A-Record von autodiscover.meinedomain.de zeigt auf dem internen DNS natürlich auch auf die interne Exchange IP.

Gehe ich von intern auf https://autodiscover.meinedomain.de sagt mir der Firefox:

"autodiscover.meinedomain.de verwendet ein ungültiges Sicherheitszertifikat. Das Zertifikat gilt nur für exchangehostname.meinedomain.de.

Da ja nur extrem wenig User ein Problem mit dieser Konfiguration haben, dachte ich es liegt einfach an kaputten User Profilen. Ich hatte mich auf einem fehlerhaften Client mit einem anderem Dummy User Profil eingeloggt und Outlook gestartet => Kein Problem nach der Erstkonfiguration

Daraufhin habe ich das komplette Userprofil vom Client gelöscht. Zack...die Warnung kommt schon bei der Outlook Ersteinrichtung. Ich kann zwar manuell das Zertifikat mit Admin Rechten in die vertrauenswürdigen Zertifizierungsstellen aufnehmen, bringt nur leider nichts.

Woran kann das liegen? Ich erkenne da keinen logischen Zusammenhang. GPOs habe ich auch schon überprüft. Sind exakt gleich. Das einzig merkwürdige ist: Es sind nur Laptops betroffen. Das kann aber aufgrund der geringen Anzahl der User auch durchaus Zufall sein.

Weiß hier jemand Rat? Danke schon mal