I believe you could do a free of charge MS case and ask support to remove the identity from previous owner's tenant. MS support does require you a proof of ownership (which you told you have, so no problem). Try to open this case via Intune portal. You don't need Azure license for that.
Anyway, this will become more and more of a problem nowadays, so it is better you figure our a test process before you buy anything from leasing company. It should be their responsibility to ensure that device hash for autopilot assignment is removed, not yours.