The P2P Foundation blog has an intriguing post about Faroo, a P2P search engine. The idea is that client computers would actual do the indexing, sharing results with other peers in the system. As the article points out, this pushes control of index data out to the peers and helps anonymize collection and usage. Basing indexing on sites users actually visit sounds as much a limitation as the advantage of avoiding spam sites. I could easily imagine the index becoming too locally optimized if the number of peers is too small, as it is likely to be early on.
The other downsides mentioned remind me very strongly of the Tor project. I can easily imagine trying to use something like Faroo to find it runs at a fraction of the speed of more traditional, centralized search engines. However, more projects experimenting with using P2P as a base architecture makes me hopeful that there is a greatly likelihood of one such project cracking some of the adoption and scaling problems.