Comment by dmichulke

You could publish a key as each of these personas and then, when reestablishing a contact using a new persona, prove your identity to that one contact by using the private key of the old (known) persona.

Am I missing something?