Solution by Event Log Doctor

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.

Solution by Samer Aqqad

Steps:
To change one of your custom e-mail address policies to a default policy
1. Install ADSI Edit if it is not already installed on the computer that is running Exchange 2007.
2. Start ADSI Edit. To do this, click Start, click Run, type adsiedit.msc in the text box, and then click OK.
3. Expand the following container:
CN= Recipient Policies\CN=\CN= Microsoft Exchange\CN= Services\CN= Configuration\DC=\DC=com
4. Right-click the e-mail address policy that you want to change to the default policy, and then click Properties.
5. In the Attribute column, locate the purportedSearch attribute, and then verify that the value in the Value column is (mailNickname=*). If the value is incorrect, follow these steps:
a. Click purportedSearch, and then click Edit.
b. Click Clear, type (mailNickname=*) in the Value box, and then click OK.
6. In the Attribute list, click the msExchPolicyOrder attribute, and then click Edit.
7. Click Clear, type 2147483647 in the Value box, and then click OK.
8. Click OK, and then close ADSI Edit.
9. Restart the Exchange Mailbox server.