Some fresh ideas are always welcome for key rotation!

Any scheme has to handle well these cases:
1. A malicious attacker quickly rotating to a new key, which the original victim cannot rotate
2. No key theft occurs, but a user just maliciously rotates away the key of an unrelated, victim user.

For Simple key deletion, 1. is ok as it makes no sense for an attacker to use. To protect against 2., the event has to be signed by the corresponding private key (if this is not enforced, anyone can delete any key; the consequence is that it is not possible to use this in case of lost key).

The Social Key Migration sounds interesting. Though an attacker could be successful in convincing enough contacts to rotate to a new key controlled by them, some contacts would benevolently and unsuspectingly help.
 

 what if the next-in-line key is pre-established?

At time of key generation the pubkey creates a timestamped event establishing which will be its next pubkey (which would be child2 of an HD key).

Upon compromise of pk1, pk2 signs a deletion of pubkey1 and signals to followers that contact lists should update to pubkey2

This is simple but addresses both points; attacker's speed is no longer relevant and only a pre-established pubkey can rotate away the pubkey. 

 Chain them together with the same approach we use in Bitcoin blocks. 

 Instead of mining a nuance, the owner would put a specific password he only knows.