I am having quite a serious issue with deleted user accounts still being present in Active Directory somewhere. We found this issue after a few users who had left the company as contractors (and had their accounts deleted) became full time employees and required new user accounts and mailboxes.
Essensially what happens is that when I create an account for one of these users, I get an error that their SMTP address is already in use. I get no warning of username being already present. For example, I create a new account for Joe Soap, his account gets created without incident, but his old SMTP address would have been firstname.lastname@example.org, and this gives me an error that it already exists. So, to get his account created, I make his SMTP address email@example.com.
The ONLY places I can see this other phantom email address is in Outlook and Exchange System Manager. If I type Joe and press ALT-K in Outlook, I get 2 Joe Soap entires. If I look at the properties of these, only one has valid data, such as Group Memberships and phone numbers etc. The other one says, "Unable to Connect to Retrieve Additional Data". If I send a message to this phantom account, I get an NDR saying "Email Address Not Found". I don't find this other address in OWA.
Before you say, "Easy to fix! Outlook has a cached copy of the GAL", I can also see the phantom address by running a preview of the Default Global Address List in Exchange System Manager. I can see both accounts in this preview, but if I try and edit or delete the bad one, I get a message saying, "Active Directory Object Cannot be Found".
I have searched for lingering AD objects using repadmin, but it says there are 0 found. I have enabled strict replication consistancy about a week ago to try and prevent any more of these problems. We have quite a widely dispersed network with about 300 domain controllers in multiple sites. All of the remote DCs are in a child domain with no Exchange Servers in that domain. I have searched in lpd and followed all the technet articles I can find about removing lingering objects. Nothing!
I have rebuilt the GAL with the Recipient Update Service a few times, but the ghosts are still there. I identified the one account as having been deleted over a year ago, so surely any cache or anything like that would have been cleared long ago.
Any ideas or advice would be greatly valued.