Searching depends on the nodes you are able to connect through. When you search, your search goes through the ultrapeers you are connected to, then spreads out through those they are connected to & so on. There is a horizon to the search however. So if you are connected to different ultrapeers, you may find different search results.

I often use Get More Results option by right-clicking search tab. I will do fresh searches every now & again. In LW 5, it's called Find More Results from memory.