(continuing above comment)...
So, reaching this point, you can:
1. restore your AD backup. (all attributes, schema changes, and domain permissions in AD should be back to SP1).
2. then you can just format the server, reset the Computer account, reinstall the box with same name, rejoin to the domain, and install exchange (with SP1 installation files) with the "recoverserver" switch.
3. After the installation, just restore your DBs, and certificate.
the server should be, back again, working in SP1.
You all may think, "something that should take an hour at most, will take me 4 or 5", yes, I agree with you. "this will require a lot of admin interaction, and work with DCs and Exchange", yes, I agree as well. "In large organizations, restoring AD will cause a replication storm", YES! I agree with you again. "what about AD changes that were performed during the upgrade time? if there was any work done in AD, that would be lost by restoring our back!", yes, but be honest with me, many times we upgrade Exchange, we demand a maintenance window, and not much changes are done in AD aside the ones we performed, the the possibility is that there are no other changes done. But...
Is it a valid workaround? YES it is! is it possible to achieve? yes it is! Are all the procedures in the workaround supported and valid by MS? yes, they are!
So, I know is not easy, but it is a workaround. At least, in the worst case scenario, you still have a contingency plan with this.
If you guys have a better workaround, please, share it with us all!!
So, that's all. And at last but not least, if MS would develop a 100% perfect product, there will be no job for us!!! the ones who offer Services, consulting and support!!! XD XD XD
(sorry for my bad english again)