Postfach wird nicht angelegt, bei neuen Usern

Hallo,
ich stehe vor einem größeren Rätsel.
Wenn ich auf dem Win2003 SBS einen neuen Benutzer anlege, wird das Postfach nicht mit angelegt (trotzdem im Dialog die Option aktiviert wurde und der richtige Server mit dem Postfachspeicher angezeigt wird).
Der User kann sich an jedem Client in der Domäne anmelden und bekommt alle Resourcen (Share, Printer) zugewiesen. Zugriff auf die Shares - kein Problem.
Nur wenn ich Outlook einrichten will, kommt die Meldung:
"Der Name befindet sich nicht in der Adressliste."
Wenn ich mich mit einem "alten" User anmelde und im Globalen Adressbuch reinschaue, steht der neu angelegte User nicht drin. Beim erstellen des Users gab es keine Fehlermeldung und in der ereignisanzeige steht auch nichts drin.
Im großen WWW hab ich auch gesucht und da stand immer nur, dass der Fehler mit dem SP1 behoben war. Der Server hat komplett SP2 installiert und alle Updates bis gestern. Noch aktueller geht es nicht.
Exchange2000 war vorher auf einem Win2000 Standard (alter Server) installiert. Alle Postfächer wurden auf den neuen verschoben und die öffentlichen synchronisiert. Bei den alten Usern funktioniert auch alles einwandfrei. Exchange2000 wurde deinstalliert und der Win2000 wurde zum Mitgliedsserver zurückgestuft. Alle FSMO-Rollen sind auf dem Win2003SBS, DNS
funktioniert einwandfrei.

Ich weis gerade nicht wo ich ansetzen soll und ich hoffe dass jemand eine
Idee hat.

Vielen Dank, M.Beier