First of all a tradeoff between a fully distributed and a client/server architecture has to be found. Both systems have advantages and disadvantages, so a crossover that minimizes the weaknesses and maximizes strongpoints is what we should be looking for. I suggest an adaptation of the FastTrack network. This network consists of a relatively small set of highly connected nodes that cache results from other less responsive systems. The caching scheme can seriously reduce overall network traffic and increase responsiveness, while the segregation of the nodes according to the quality of the resources will ensure no unnecessary bottlenecks in the network occur. Frequently reviewing the state of the network increases robustness and allows for an automatic stabilization in the dynamic environment. A generalization of the 2-level hierarchy to more illusive structures based on the same dynamic principle could reduce overhead even further.
Alternatively, the system can be modeled after the Alpine(16) network. This implementation does not rely on rebroadcasting by peers. Instead, a node broadcasts (or multicasts if possible) its message using the unreliable UDP protocol to all known nodes at once. Minimizing the size of these initial messages together with the lack of indirection could very well make this a viable method of communication initiation. When a node has an answer it can then set up a reliable direct link using for instance TCP. This system might work especially well when reducing the number of nodes that may respond to the initial message. For this cause a caching scheme could be implemented. It is then basically reduced to the previous system, but without the complicated bottom up query forwarding.