Rebuild Domain

I failed moving mailboxes from Exch55 on NT4 to Exch2k on Win2k DC, and even not allowed me remove all the Exch2k components from Win2k DC. We assumed it’s AD issue and try to figure out the possibility of DOMAIN REBUILD and installing a virgin domain and fresh Exch2k, then move pst from each workstations. Anyone out there ever done domain rebuild before.
Here is our background,
1 Win2k DC with AD
1 NT4 BDC with exch55 (both they will retire)
12 W2k clients and others are W98.