Yeah, that's an interesting problem and would make sense in that context. They wouldn't be encrypting it when the data needs to be deleted, but encrypt it from the start, keep the key offchain and delete the key when they are required to delete the data. The data would still be "available" ("it's in there somewhere, but we have no way to get it out"), but useless. Would be necessary to make sure that no metadata can be gathered from the encrypted data on the chain, so when my doctor deletes the key, you mustn't be able to ascertain that I was even a patient.

I don't know whether it would hold up in court though, but it's an interesting idea. With a private block chain, the risk would be a lot smaller that a single leaked key (i.e. the customer accidentally releasing it) would result in big problems. I've recently talked with a lawyer friend of mine about a similar topic, but he didn't know immediately whether that's legally sound.