[peterwwillis]

Use the same method you use to pay for the domain to reset the key. This would require logging into your account at the registrar, or contacting support and providing enough verifiable material to reset it.

If the registrar signed a message that had your key in it, they could re-sign it with a replacement key. So now you can 1) verify who originally assigned the domain, 2) record the public key, and 3) see a verifiable history of changes as long as the old history is included in successive signing. This could be used as part of a public record ala Certificate Transparency, or a blockchain-style system. If the attacker spoofs BGP and SE's your registrar, you (or whomever) can see if anyone creates a new key.