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.