Nach fünf (!) Jahren hole ich das Thema nochmal raus um es dann mal abzuschließen.
Ich hatte vor ca. 2 Jahren die Mailprofile in die User Verzeichnisse auf dem Server gelegt und diese mit dem Profilmanager 'angemeldet'. Seitdem ist das Problem nicht mehr aufgetaucht.
Irgendetwas war wohl an der Profilreplikation vom und zum Domänenserver nicht in Ordnung. In anderen Umgebungen scheint es ja zu funktionieren.
Da im Zuge der Win10 Umstellung die Domäne abgeschaltet wurde kann das Problem nicht mehr auftreten.