Fortunately it was a relatively small environment with a single Exchange 2007 server and about 120 mailboxes.
Here's what we did:
- use ADSI Edit to completely remove the existing Exchange organization
- completely wipe out and reinstall Windows on the Exchange 2007 box
- reinstall Exchange 2007 creating the same organization name
- recreate the storage groups and copy databases into the storage groups.
- Disable and reenable all users in EMC to recreate Exchange attributes
- Disable and reenable all distribution groups in EMC to recreate exchange attributes
- Configure certificate and smtp connectors.
Basically a whole rebuild. In retrospect, I should have tried just running /PrepareAD to see if that resolved the AD issues.
Note that the organization name needs to be the same during the reinstall or the databases will not mount.