We recently had a problem with an Exchange server running Windows 2003 server standard and enterprise exchange. We recabled the entire network, but did not perform any address changes. However, the exchange server would not boot correctly after restart. The Windows Server would hang on "applying settings" - unless you unplugged the NIC. If you unplugged the NIC, the box would use your cached local account and allow you to log in.
At any rate, I checked the two domain controllers for signs of problems - but could not find any. The error in the event log on the exchange server was event 9157. There was an MS article vaguely relating to it (http://support.microsoft.com/kb/297295) - but the exchange server's account was definitely present in AD users and computers. In spite of that, I did use ADSI Edit to make the suggested changes in that article, but it did not help.
As it turned out, someone had remove the Exchange security groups out of the default users OU a month before this happened. It just so happened that the exchange server had not been rebooted since then. I'm guessing that one of the group policies didn't apply - as it was probably hardcoded to an entry in ad users and computers
I moved both of those groups back to the users OU, and restarted the exchange server; it came back up after reboot. What I guess happened was that