If a CRM user’s Active Directory account is deleted then the user will not be able to use CRM. Recreating a new AD account with the same will not work because all AD accounts have an identifier that is unique regardless of the actual account name.
It is possible to update the CRM user record to use the re-created AD account though the process is not obvious.
Open the deleted user’s CRM user record. In the Domain Logon Name change the logon name (and domain) to any other AD account (it is important to choose an account with a different name otherwise the CRM record won’t get updated). Save the record. Now, update the Domain Logon Name to the re-created AD account and save the record.
The deleted user should be able to get back into CRM. If the logon name you created for the user was different from the deleted user or you want to connect the CRM user record to another AD account you won’t need to go through the step of using another AD account temporarily.