All that would be needed is for anyone selling a phone to provide the imei and some id to a govt service to assert that they are the current owner and intend to sell it for x price on y day. If you don't do this check and buy a phone, you're held liable if it is stolen. If you do, and it passes but later turns out to be stolen, automatically reimburse the buyer when you return it to the owner and make the seller liable to cover all associated costs in addition to the handling stolen property.

Most of this is already implemented for cars via vin, and doesn't require that an unelected central power has carte blanche to do whatever they want to it at any time.

Have a central database of registered owners.

Allow current owner to assert that they own a given imei in a way that the buyer can check on said database.

Register the transfer of ownership during sale.