Recently I was looking for a thread and gave up. I knew what was in the subject of the thread but had no idea what category. What about providing an option in the dropdown for searches to search "Everywhere" to include every possible category (bypass it in the query). This way regardless of where it was posted it can be found.
I'd imagine the only time it would consume server resources is when there is an "Everything" search that goes through every thread in the system. Whereas a "Everything" search that would only search the "Subjects" of everything would be by far less resources.