1) It's not possible to search the whole network, - gnutella wasn't designed to do that. (Searching 50%-80% of the gnutella network depending on the time of the day and the quality of your ultrapeer connection is about the best you can achieve with LimeWire)
2) Gnutella clients are supposed to do AND-searches. Searches for "key1 key2" should only return queryhits containing key1 AND key2. But LimeWire doesn't check this, it expects all other clients to comply with the protocol specs.
3) Busy clients cannot always be searched. Some just drop queries if they are busy (I think newer LimeWire's do the same under certain circumstances). So even if the host you are downloading from were in your search horizon you might not see any results from it.
4) The LimeWire versions 2.9.9 - 3.1.0 have a bug that keeps you from searching their leaves.