Device already enrolled iOS enrollment error

[kkeirstead]

We have a few users that are currently unable to enroll their devices into Intune. Under the troubleshooting blade under enrollment failures it lists "Device already enrolled". I've seen this error before and typically I would go to all devices -> search with the SN and then delete the old device record. However ever since we turned on Device Clean Up rules, the devices are deleted but the users are still unable to enroll (Before configuring device clean up rules I did an export of all devices and I can see the old device record located in that export). I went into the Device Enrollment -> Apple and tried to reassign the DEP profile but that doesn't seem to fix the issue. Has anyone seen this or know how to fix?

[#2]

How was the device enrolled by the end-user? Was it wiped/restored then enrolled via Setup Assistant (DEP) or manually via the Intune Company Portal client app. It might be worth checking the end-user device to make sure that all the payloads from the previous enrollment were removed successfully. I've sometimes seen iOS devices retain profiles even after being removed from MDM.

[#3]

Did you check Azure AD if you can see the stale device records.  If they are still there, remove those and try again. 

Thanks,
Shuchi

[#4]

Are you having any issues with the enrollment certificate?  Would explain why new users are having issues, but ones that are currently enrolled are not.