@AliciaXO, Thanks for posting in Q&A.
From your description, I know you want to remove old work account but failed.
Based on my research, it can be removed from Intune portal. If possible, you can give the Serial Number/IMEI of the Android phone or you Android device name to the security group or IT department in your former company. They may search by the Serial Number/IMEI and find your phone, then remove it from Intune portal. And then you can add new company details in company portal app.
Or you can refer below steps.
Microsoft Intune company portal is a device admin app in your android phone. So, you can go to below location in your phone and turned off it in device Admin.
Settings>Privacy Protection>Special Permission>Device Admin Apps
After that remove your email or uninstall company portal and outlook.
This step will help to remove your device with your previously linked company, and you will be able to connect to your new company.
Hope above information can help you and if there is any update, feel free to let me 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.