Perhaps the songs you're after are not being shared or else, the people who do have them don't have free slots, or they use one of the other gnutella programs such as shareaza which can be extremely difficult to connect to. If you find there's like 100 results for it, then those ones may well be spammed fake files you will never downld. Instead, look further down the search results for those with less than 20 hosts under the # column.

Another option is to search for other songs by the same artists, then browse those people. They may well have the ones you're after.