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.