Ich würde sagen, das in Deiner Umgebung ein paar generelle Probleme am argen sind, welche sich nun bei der Exchange Installation gezeigt haben. Diese fangen bei der AD an und gehen über DNS und WINS. Wenn da was nicht sauber ist kommst Du zu den bestehenden Problemen.
Ist es denn eine produktive Umgebung oder noch ein Testlab??
Wie hoch ist den die Benutzeranzahl?
Wenn der Neuaufbau das Forest nicht in Frage kommt, musst Du als erstes sicher stellen, dass die Exchange Organisation sauber entfernt wurde.
http://www.msexchangefaq.de/e2k/e2kremove.htm
Wenn der Schritt geschaft ist prüfst Du Dein DNS & WINS.
Dann sollten Ausserdem keine Fehlermeldungen mehr im Eventlog zu finden sein.
Gruss
Heinz