You should be able to search with just outgoing connections. Incoming connections are other users that connect to you to access the GnutellaNet. While they may improve your search results, they are not a necessity.
Your search problem is probably caused by somthing else.