@Hull, Allison Thanks for posting in Q&A. For the error message, it means the device is still managed by the previous tenant. To unenroll the device, the general step is contacting your previous company Intune admin to retire or delete the device in both Intune and Microsoft Entra portal.
https://learn.microsoft.com/en-us/mem/intune/remote-actions/devices-wipe#retire
On device side, we can also unenroll the device via company portal.
https://learn.microsoft.com/en-us/mem/intune/remote-actions/devices-wipe#manually-unenroll-devices
I notice you have already tried to remove Intune app. But it is not working. If this is iOS device, you can also try to remove management profile under Settings-> General on the device to see if it works.
For Android device, you can try to remove the work profile to see if it works.
https://support.google.com/a/users/answer/7579983?hl=en
Note: Non-Microsoft link, just for the reference.
Another method I can think is to backup the data and factory reset the device.
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.