It sounds like the domain may have been converted from managed to federated while the user was in the recycle bin. If this is the case, the user will not have a source anchor, and the restore will fail since federated accounts can only be created in the system of origin.
You could potentially resolve this by changing the domain back to a managed domain.
If the information helped address your question, please Accept the answer. This will help us and improve searchability for others in the community who may be researching the same error.