I've figured this out yesterday. Turns when a user is deleted, it goes in a deletion queue but the account is not really deleted. After I did an advance search for "Queued removal of BlackBerry services = True" I was able to find the user I was looking for and delete the record properly.
Thanks everyone for all your help.