User Profiles are not deleted from the User Profile Service once a user is deleted from Active Directory. You must manually delete them or purge them with some PowerShell. The way to do this is shown below.
- Open SharePoint Management Shell as an administrator on one of the SharePoint servers in the farm.
- Run the PowerShell command Get-SPServiceApplication. This will give you a list of all the service applications and the associated GUIDs. Get the GUID for the User Profile Service.
- Run the PowerShell command below with the GUID from the User Profile Service.
$ups = Get-SPServiceApplication -Identity <GUID of UPS>
i.e. Get-SPServiceApplication -Identity e2c2be70-6382–4ce7-8a44-ae7dadff5597
- Next run the following two PowerShell commands to purge the deleted User Profiles.
Set-SPProfileServiceApplication $ups -GetNonImportedObjects $true
Set-SPProfileServiceApplication $ups -PurgeNonImportedObjects $true
Note: As always it is important to do a back up before you purge anything. The default database for User Profiles is Profile DB. It is recommended that you back the profile database before you perform this operation.