If you can distribute your information over a set of reliable and trustworthy nodes, this could work very well. However, we can't assume any one node to be reliable, so we need to build in a good deal of redundancy and dynamic replication.
Hm, not easy to find anything on this but I can't think of any way to do better than have statistical assurances (i.e., 10 servers say it doesn't exist so it probably doesn't).Yes. This is a problem with classic design of DHT. But, recently there are lot of DHT proposals in a byzantine environment (viceroy etc..)