1) Build the server the way you want with the basic OS, patches, etc.
2) Add the system to the domain.
3) Promote the system to being a domain controller.
4) Validate that the system is properly replicating data (replmon, eventlog messages, dcdiag, etc). You may want to let it sit for 24 hours, just to see that everything is running well.
5) Migrate the FSMO roles over to this server. I like to use NTDSUTIL to perform this, mostly because then I can move all of the FSMO's from one place instead of 3 different tools. I know I have described this process before, and as well Microsoft has se
veral articles with easy steps like this one: http://support.microsoft.com/default.aspx?scid=kb;en-us;255504&Product=winsvr2003 6) You can now install Exchange 2000 on the machine.
7) Configure Exchange the way you like and make sure you match the SP of the other server.
8) Create a new Information store(s).
9) If you do not have too many users you can migrate them from one server to the next by using Active Directory Users and Computers. You right click on one or more users and then click on the Exchange features and move the users to the new server. This will move all of their data too. If you have a lot of people you want to move, I would suggest EXMERGE. Using this tool also gives you a method for creating temporary backups of the data prior to the move if you like. Here is an article that I have used before. It has some nice references to other materials on Exmerge as well: http://support.microsoft.com/default.aspx?scid=kb;en-us;328810&Product=exch2k
10) Once all of the users are removed from the Exchange server, uninstall Exchange from the old system. You will want to uninstall as opposed to simply turning it off. This is a little cleaner. You may still need to use the Exchange Admin on the other machine to clean up any residuals left.
11) Demote the server -- again a lot easier than manually cleaning things up.
12) If you intend to retire the system, take it out of the domain completely.
13) Shut it off.
There you have it.