Today I came across a very odd issue where I had seen a number of missing SharePoint User Profiles missing from the Active Directory synchronization.

The problem was, the deleted Active Directory users were left in the User Profile database marked as deleted, but never deleted by the “My Site Cleanup Job”. You can query the UserProfile_Full table to determine which profiles have the bdeleted column set to 1.

A description of the timer job is displayed below:

It turned out that the solution was to ensure a My Site host had been configured as part of the farm setup, so that the missing profiles from import are correctly removed. The My Site Cleanup Job runs every hour,  by default, and even though the job looked as though it ran successfully it wasn’t actually performing the specified function.

You can follow this Microsoft TechNet Article to configure a My Site Host in your farm.