The only supported method to remove servers is to do a DR install. That means resetting the computer account in the domain - DO NOT DELETE THE COMPUTER ACCOUNT - then building replacement machines with the same name and adding them to the domain.
Then install Exchange 2007 using the /recoverserver switch.
http://technet.microsoft.com/en-us/library/bb123496.aspxOnce done, you then remove Exchange correctly using add/remove programs.
-M