I understand why folks aren't happy this isn't a perfect solution.
But IMHO slightly modifying the flow makes this work fine (tried and tested with two of our customers):
0. Inform users of upcoming changes and which steps to take.
1. Reset/wipe device remotely from Intune. This'll take a while - between 15 and 90 minutes, depending on the device.
2. THEN delete the Autopilot records, immediately after Intune reports the wipe was issued/queued.
3. Upload AP IDs to new tenant.
4. Users rejoin.
5. Repeat with devices that somehow didn't make it.
Obviously, there is a brief period when users' devices might not get captured by Autopilot (neither old nor new tenant) and can, in theory, get hijacked outside of company management. Or, users just can't get to work.
Hijacking (for example by using a personal account during OoBE) doesn't seem to be an issue, since folks really just want to get back to work. And on Enterprise images, that isn't possible anyways.
To ensure smooth transition, here is how we informed users:
a) Once your device has reset, please verify you are being welcomed by your new company when your PC starts up. Unless you are being welcomed by your new company (ie branding), DO NOT PROCEED and just turn your device off. There is no danger or risk in doing so. (optional: add what to do if someone ends up in WinRE)
b) A few hours later, or the next day at the very latest, when you boot up your PC, it should welcome you to your new company and prompt you to sign in with your new credentials. Then please do so and grab a coffee or two while we set up your PC for work in your new organization.