It's definitely a tricky problem; the DID spec (which you may find interesting if you haven't read it) tries to allow for ways for keys to be revoked or even replaced even in the case of key loss (basically, here's 5 people I'm baking into my identifier by saying I trust them, if three out of five say that actually $X is my new key, that's enough to replace it) but obviously that too can have sharp edges...