Some more questions:

Are your bars fully lit up on the bottom left of your screen? [Full connectivity]

If you aren't an active Ultrapeer, you shouldn't be getting many queries in the incoming queries panel, so don't worry about that.

Can you give an example with screen shot of a search that isn't performing?

Have you tried disabling your Firewall altogether and seeing if that fixes it so we can trace it back to being a firewall issue?