Deleted users are still on the domain.
The cause of deleted users not being picked up is a permissions issue on the domain.
To resolve this you need to configure the service to run under an account with domain administrator rights.
Steps to resolve:
1. Create a new user in Active Directory and grant them Domain Admin privileges.
2. Run Services.msc and highlight sps-manager.
3. Right-click and choose Properties.
4. Click the Log On tab, check This Account and enter the username in the format NETBIOS\username, then enter and confirm the password.
5. Click Apply and then restart the service. When you click Sync now, deletions will be detected