PrepareAD fails running the Exchange Server 2010 setup

The Problem
We got into a problem recently at a customer site when running the Exchange server 2010, setup.com /prepareAD switch in an Exchange Server 2003 environment. The command failed and exited with the problem pointing to the “Default Global Address List”, according to the error message in the exchange setup log:

[ERROR] Active Directory operation failed on dc1.example.internal. The object 'CN=Default Global Address List,CN=All Global Address Lists,CN=Address Lists Container,CN=ExampleOrg,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=example,DC=internal' already exists.

Research
We searched for the error message on similar cases on the Internet which indicated the need to recreate the “Default Global Address List”.
We didn’t see the missing Default Global Address List, however a new similar empty list called “Default” was there when looking in the Exchange System Manager. Did the customer rename the *Default Global Address List” to just “Default”? The LDAP filter for this “Default” was empty and we couldn’t rename it to “Default Global Address List” or create a new ”Default Global Address List”, it already exists according to the error message.

Found a strange object “Default Global Address List” which was empty of any attributes in the "All Global Address Lists" Container when looking at it with ADSIedit. The only attribute we could see was the Distinguished Name (DN) of “Default Global Address List” in the All Address List Container and another equally strange object “All” with also only a DN and no other attributes populated.

We opened the LDP.exe tool and looked at the object with the same result, couldn’t see any other attributes than the DN of the object, no USN, no WhenChanged, no WhenCreated date, no GUID, nothing but the DN.
Our theory here was the customer had somehow removed the “Default Global Address List” in an unsupported way, and that the remaining object was now some sort of leftover.

Troubleshooting
Tried to delete both "leftover" address lists with ADSIedit, only to get the following error:
---------------------------

Operation failed. Error code: 0x8007200a

The specified directory service attribute or value does not exist

Could it be permission issue, changed the permission for Everyone and Authenticated Users, which had Explicit Read Deny?
Tried to delete both of the "leftover" address lists again with ADSIedit, which resulted in the following error:
---------------------------

Operation failed. Error code: 0x80005008

One or more input parameters are invalid

At least now we knew that we were on the right track and now we could actually see the Default Global Address List in System Manager.

Solution
We removed all the explicitly set permissions for Authenticated Users and Everyone group (we don’t want our users to see all recipients since it’s a hosted solution with many companies and multiple address lists), which also removed any Deny permissions.
We rerun the command d:\setup.com /PrepareAD switch and everything worked just fine this time.

Root Cause
It was the Deny Read permission for the Authenticated Users and Everyone group that blocked the setup program from running the /PrepareAD.

So the root cause to this problem was that the customer in his effort to hide the “Default Global Address List” probably made an administrator mistake and denied everyone the rights to read the “Default Global Address List”. The correct way should have instead been just to remove the Read permission for the Everyone and Authenticated Users Group. This change denied both the administrator and the System the right to read the object. When the Exchange Server 2010 setup run, it couldn’t read and find the “Default Global Address List” during the /PreparedAD phase, it then tries to repair and fix the problem by recreating the “Default Global Address List”, which also fails since the object is still there with its Distinguished Name “ Default Global Address List”.

Following are the interesting parts from the
ExchangeSetup.log confirming the troubleshooting result.

[04-23-2010 10:02:32.0089] [1] Executing 'install-GlobalAddressLists -DomainController $RoleDomainController' failed. The error is: False

[04-23-2010 10:02:32.0089] [2] Launching sub-task '$error.Clear(); install-GlobalAddressLists -DomainController $RoleDomainController'.
[04-23-2010 10:02:32.0105] [2] Active Directory session settings for 'Install-GlobalAddressLists' are: View Entire Forest: 'True', Configuration Domain Controller: 'dc1.example.internal', Preferred Global Catalog: 'dc1.example.internal', Preferred Domain Controllers: '{ dc1.example.internal }'
[04-23-2010 10:02:32.0105] [2] Runspace context: Executing user: Example.internal/Users/Administrator, Executing user organization: , Current organization: , RBAC-enabled: Disabled.
[04-23-2010 10:02:32.0120] [2] Saving object "\Default Global Address List" of type "AddressBookBase" and state "New".

[04-23-2010 10:02:32.0167] [2] [ERROR] Active Directory operation failed on dc1.example.internal. The object 'CN=Default Global Address List,CN=All Global Address Lists,CN=Address Lists Container,CN=First Organization,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=EXAMPLE,DC=internal' already exists.
[04-23-2010 10:02:32.0167] [2] [ERROR] The object exists.
[04-23-2010 10:02:32.0183] [2] Ending processing.
[04-23-2010 10:02:32.0198] [1] [WARNING] <<< setup failed to execute a task. Dumping all variables.... >>