Based on your update to the symptom, I suspect a problem with AD replication and Exchange. Microsoft has a report on this at http://tinyurl.com/2rh7f
Specific steps can be found at http://tinyurl.com/2ehel.
The summary of steps is:
Temporarily turn off the ADC by either stopping the service or setting the schedule of the recipient Connection Agreements to Never.
Remove the ADC-Global-Names attribute from all Exchange Server 5.5 recipients including the custom recipients that were created by the ADC.
To perform this step, you can either edit the recipients in raw mode or use the Directory Import/Export functionality.
Delete the custom recipients that were inadvertently created by the ADC in the Exchange Server 5.5 directory.
NOTE: You must remove the ADC-Global-Names attribute from the custom recipients before you delete these objects. Tombstones of these objects may cause problems if they still contain an ADC-Global-Names attribute.
Mail-disable all of the affected Active Directory user accounts including the disabled accounts.
To perform this step, you can use either the Killmail utility or the Exchange Tasks functionality.
Delete the disabled user accounts that are created by the ADC.
Verify that the previously affected accounts no longer have an e-mail address, turn on the ADC, and then force replication.
