This error comes in because the device to which user is trying to login is already deleted from Azure AD.
I understand that you had deleted few devices from AAD as you were getting an error.
But it looks like there are other users also who are trying to login to deleted devices. If this is the case then you will have to recover the deleted devices from Azure AD.
Azure AD do not have any recycle bin for deleted devices. But you can perform below steps on the deleted devices itself and get the device identity back in Azure portal,
For Azure AD joined devices Windows 10/11 devices, take the following steps:
- Open the command prompt as an administrator
- Enter
dsregcmd /forcerecovery
(You need to be an administrator to perform this action). - Click "Sign in" in the dialog that opens up and continue with the sign in process.
- Sign out and sign in back to the device to complete the recovery.
Do let me know if you have any further questions.
Please "Accept the answer" if the information helped you. This will help us and others in the community as well.