@Chase Maldonado, Thanks for posting in Q&A. Based as I know, Azure AD joined devices will be enrolled into mobile device management again when an Azure Active Directory enabled user signs into the device after doing Fresh Start. But from your description, it seems the device is not enrolled again.
Here, we suggest check if the new user is with both Microsoft Intune and Azure AD Premium license assigned. And if the new user is in the MDM user scope of Automatic enrollment.
Please check the above information and if there's any update, feel free to let us know.
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.