@TechUST, Thanks for posting in Q&A. For these accidently deleted devices, please go to the device side and clear the registry key under HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Enrollments to remove residual information.
Meanwhile, remove the Intune related device certificates on the device.
After that, configure "Enable automatic MDM enrollment using default Microsoft Entra credentials' enable and select User Credential from the dropdown Select Credential Type
Then you can perform gpupdate /force to apply the GPO to re-enroll again.
In addition, please ensure the Microsoft Entra Premium and Microsoft Intune Plan 1 licenses are assigned to the user.
Hope the above information can help.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.