"Deletion-compliance relay crawlers" sending then deleting notes from random nsecs could do a reasonable job of flagging relays that didn't comply (whether they claim to or not).

Couldn't detect "logical deletion" this way, though. So likelihood of a copy somewhere is high.