If they are able to log into the PCs then the accounts may still exist locally, in which case you would still need to delete the users from the local Active Directory.
Also, if the accounts were only recently deleted they might not be entirely gone.