Halle an alle.
Ich habe die Ursache ermitteln und das Problem beheben können.
Schuld waren fehlende / fehlerhafte Schreibrechte im AD.
Im AD habe ich die Container-Ansicht für Benutzer aktiviert und bei den betroffenen Nutzern das CN für den Exchange ActiveSync gelöscht. Danach habe ich die Mailbox im jeweiligen Mobilgerät nochmal neu eingerichtet und alles funktionerte auf Anhioeb (das CN wird dann im AD neu angelegt).
Die eigentliche Ursache hierfür wie dies entstanden ist, ist mir nicht bekannt aber die Lösung (nachdem einmal bekannt) ging sehr schnell und ich betrachte das Thema als gelöst.