Granted this could be mitigated if only 'trusted introducers' (TI) are able to add deletion tokens ( but as long as the protocol is open, this, itself, would require a lot of thought on implementation. E.g by adding an element to the key to be deleted that is signed by the TI.
I think it would be a mistake to implement deletion in the way I described without some notion of trusted introducers. And that should I think be implemented by having a set of keys that the full network trusts to introduce deletions. As I said, there is real work getting the code to make this happen, and also doing the social work of choosing the trusted sources.
y