1. A method comprising: at a first peer node in a peer-to-peer network having a plurality of peer nodes in which connections among some of the plurality of peer nodes cannot be formed because a number of hops among such nodes is more than a maximum number of hops allowed for the peer-to-peer network, the steps of: connecting to a second peer node to form a direct connection; issuing a search request message to the second peer node over the direct connection, the message requesting the second peer node to forward the search request message to other peer nodes of the second peer node; receiving a response to the search request message from the second peer node including one or more responses from the other peer nodes of the second peer node, the response including peer node distance information; determining from peer node distance information provided in the response, which of the other peer nodes of the second peer node is a determined peer node, such that a number of hops along a path from the first peer node to the second peer node to the determined peer node is equal to or greater than a maximum number of hops that the search request message may be forwarded using the direct connection to the second peer node: maintaining connection information received from the plurality of peer nodes, the connecting information including information about connections among the plurality of peer nodes; accepting or denying a search request received by the first peer node from a requesting peer node, the search request requesting to connect to another peer different from the requesting peer node and the first peer node, the accepting or denying based on the connection information maintained by the first peer node and received from peer nodes other than the requesting peer node; connecting directly to the determined peer node to form a direct connection to the determined peer node that is in addition to the direct connection to the second peer node; issuing a second search request message to the determined peer node requesting the determined peer node to forward the second search message to other peer nodes of the determined peer node; receiving a response from the determined peer node including responses from the other peer nodes of the determined peer node; and determining from peer node distance information provided in the response from the determined peer node, which of the peer nodes of the determined peer node is a second determined peer node, such that a number of hops from the first node to the determined peer node to the second determined peer node is equal to or greater than a maximum number of hops that the second search message can be forwarded using the direct connection to the determined peer node.