Hallo testosteron,
ich hatte exakt das gleiche Problem.
Bei mir hat es geholfen, auf dem Server, auf dem auch Exchange läuft, im Internet Explorer über die localhost/owa zu gehen.
Dort habe ich mir das entsprechende Zertifikat exportiert und am Client in die Vertrauenswürdigen Stammzertifikate importiert.
Anschließend konnte Outlook ohne Sicherheitswarnung gestartet werden - auch ohne Computer-Neustart.
Ich hoffe, dass dir das noch hilft - immerhin ist der Post bald 7 Jahre alt :)
Trotz Zeitdifferenz dir noch viel Erfolg.
MfG
Daywalker