Peer-to-peer (P2P) computing is an intriguing paradigm for Web search for several reasons: 1) the computational resources of a huge computer network can facilitate richer mathematical and linguistic models for ranked retrieval, 2) the network provides a collaborative infrastructure where recommendations of many users and the community behavior can be leveraged for better search result quality, and 3) the decentralized architecture of a P2P search engine is a great alternative to the de-facto monopoly of the few large-scale commercial search services with the potential risk of information bias or even censorship. The challenges of implementing this visionary approach lie in coping with the huge scale and high dynamics of P2P networks. This paper discusses the architectural design space for a scalable P2P Web search engine and presents two specific architectures in more detail. The paper's focus is on query routing and query execution and their performance as the network grows to larger scales.