Can you try updating to Market 4.0 to see if that resolves the issue? You can download it from your Purchase History page.
It shouldn’t make a difference, but … you know how that goes…
If it does not make a difference, can I please get a temp admin account so I can take a closer look?
My guess is that a plugin is likely unsetting the search query vars. You can test this by temporarily deactivating all other plugins. I have a hunch that will solve the problem. If it does, then you have to activate the plugin one at a time until the issue comes back. When it you’ve found the plugin causing the issue. Let me know what you find out.