I agree, at least afaik there is no way to construct a formal "Proof of Deletion". This risk though I believe exists with even centralized services, so for example if I ask Amazon to delete this blob of data I actually don't know if in fact they did delete it. We all just assume they are doing what they are purporting to do, because if they aren't then there could be significant legal repercussions.
In the Filecoin case, I would still think that it should be possible to guarantee that a particular object is not being actively served by a node on the network at any particular point in time and penalizing nodes (loss of Filecoin) that do not pass this check.