5000MSExchangeISUnable to initialize the Microsoft Exchange Information Store service. - Error 0x80004005.
This error started appearing after we added a sub domain to our AD domain. This error prevented the IS to start during reboots, but a manual starts after a reboot would always succeed.
To resolve this problem:
* Open Exchange System Manager
* Expand "Servers" and right-click the computer where this problem appears
* Select "Properties" and go to the "Directory Access" tab
* Make sure that you have the domain controllers for type "Config", "DC" and type "GC" manually listed in there.
This should solve the problem.