You could also do some kind of distributed proof that they still have it: ask every host that claims to have a file compute the hash(prefix+content) of the file

You could also do some kind of distributed proof that they still have it: ask every host that claims to have a file compute the hash(prefix+content) of the file, where prefixes differ: distributed k prefixes to each client, and then compare them to get a proof that at least some number of copies exist.