I suppose that you first deleted the accounts from active directory and then try to delete them from SQL Server?

If so:

Try to get hold on to the SUID of these deleted users. The suid is kept in the database.

To avoid this kind of trouble:

Make a active directory group, where each account from active directory is a member. This way you never have to delete an active directory account from your SQL Server login list.