What client are you using, BearShare, LimeWire, etc.?
Once you get connected to some hosts you shouldn't have problems getting good search results. Last I heard BearShare was returning the most search results.
On the Gnutella Network searching it not that hard, the hard part is finding someone to download from that is not busy.
