I'm sorry, but I have to strongly disagree with you. Delete requests honoring can't be enforced on the protocol level. And the idea that it can be done and users could rely on it is dangerous. 

For relay to be compliant with the protocol (now or in the future) is enough to not return deleted notes, but you can't make sure that there is no copy of the old notes. Maybe they are still in the database with deleted flag, or they are in backups or they were broadcasted to a private relay not accepting kind 5 at all and you can't query it... 

By changing the wording in NIP-09 from SHOULD to MUST you are not going to change the reality. The only thing which happens is that users will get a false hope of security. 

Most of the relays and clients are honoring the delete requests to the extant that you can get rid of typos or accidental likes. This is good enough for me, but I do automatically assume that bad actor can have all my notes and keep them indefinitely. 

You are right about the one key pair being dangerous if leaked and the idea of using child keys for different services and applications is something we should be talking more.