Can MDM be permanently removed from a preowned corporate device?

We have an old corporate device, purchased preowned, clearly the owner sold us his old work phone, unknown to us at the time...

We received the device completely factory reset, but when starting it, I could add my apple ID and set up the profile, no prompt for MDM log in or anything, but then it becomes clear in the settings that the device is supervised. Our only choice was to use 3rd party software to remove MDM, in this case we used some random one found on google, Unictool I believe it was called. That's done the job, the MDM is removed as far as I can see in settings. The issue is this only works if I create a whole new set up - so same apple ID but cant import all of my apps, passwords etc. - and if I factory reset the phone then the MDM seems to come back, so clearly the MDM is not being permanently removed (it must be deep in the device somewhere and not linked to the apple ID - excuse my poor IT/system knowledge!).

I could set up this new profile, re-download all apps etc. - but I do worry that if I ever had to reset my iphone then the MDM would come back and i'd have to download and pay for this 3rd party software again just to get it off (and do the whole apps download over again).

I also have a concern that if I go through all of this work, then backup this version of my phone, will the backup contain an MDM profile that will then be passed onto another device etc. in the future (never ending trap cycle).

Sorry for the long winded question, but I really can't understand why MDM can't be removed with a restored profile, given the profile being restored never had MDM in the first place, it's the phone with the MDM/DEP and never my apple ID - I cant get my head around why I have to create a whole new profile from scratch for the MDM removal software to work.

Is there any way to remove it, ensure it never comes back, and bring my profile over from my old iphone to the new iphone?

I am also scared that maybe the software just found a way of making it look like it's removed (overwriting the display of the settings or something if that's possible?) rather than actually removing the MDM, and I worry that the device it being tracker by its former owner's company and they could simply shut it down at any time

Thank you in advance

[Re-Titled by Moderator]