Exchange User will nicht

neue Exchange User findet man nicht im Adressbuch

Ich habe ein Windows Business Server 2003 hier stehen, den ich nun als Netzwerkadministrator zu betreuen habe.
User im AD hinzufügen habe ich alles ohne Probleme bewerkstelligt, ihnen wärend dessen ein Exchange Konto generiert auch.
Also sie haben Exchange Rechte und sollten sich nun in per Outlook 2003 einloggen können.
Alle User die schon angelegt waren, also die ich nicht gemacht habe, findet man auch und kann sie benutzen.
Doch die User die ich angelegt habe, bekommen eine Meldung: "Der Name befindet sich nicht in der Adressliste."
Habe schon den RUS Service eingestellt und auch schon X mal auf jetzt aktualisieren geklickt, doch es hat nichts gebracht.
Es ist egal welcher PC und die Einstellungen darauf, alte User kann man benutzen meine nicht.
Im System Manager werden sie ja erst Angezeigt sobald man sich einmal eingeloggt hat, aber das geht ja gerade nicht.
Verbindung zum Server besteht 100%ig!

Habe auch schon die Exchange Postfächer gelöscht und wieder neu gemacht aber es hat nichts geholfen.
Die User im AD hab ich auch schon neu gemacht aber alles nix. Weiß nicht woran das liegen kann...

Der Exchange Server is in der Version 6.5 ( 6944.4 ).

Danke schonmal

mfg
Thomas