Been done. Gnutella et. al. were doing distributed search by design, because Napster's central index was ruled to be infringing. Everything old is new again...
A better alternative would be to find a way to dump the searchable information in "the cloud", but encode it in such a way to make it very difficult to detect or differentiate from "normal" content. The clients would know how to read and even search this "subliminal channel", and use it for rendezvous, etc.
"Cloud" could really be any public hosted online content, a social bookmarking site like reddit, S3, etc. I wonder how much data you could even stash inside flv video or mp3.
I'm not saying this would be easy, it would need to be redundant enough to withstand constant takedowns, etc. but it would be much more difficult to stop.