Hallo,
also, wenn der DC und Exchange verschiedene Server sind, kann das schon dauern.
Die Informationen werden ja alle über das AD repliziert.
Ich vermute dahinter ein DNS / WINS Problem.
Kannst du mal die LAN / DNS / WINS - Einstellungen der beiden Server sowie der Clients posten?