Why do multiple WHERE conditions slow query rather than speed it up?

The only way to know why is to check the execution plan. Try SET SHOWPLAN_TEXT ON.

Get an execution plan

You need to look at execution plan in order to have any hope in understand the real reason for the variation in response times. In particular in this case there are several factors to consider:

• It's possible that some of the queries returning more rows are faster because they are doing table scans - everyone has "table scans are slow" drilled into them, but depending on the data distribution it could well be faster to do a table scan than 50,000 row lookups. Its simply not possible to tell without an execution scan.
• It's also possible that incorrect statistics are preventing SQL server from accurately predicting that number of rows that its expecting to return - if SQL server is expecting 20 rows but there are really 20,000 then in more complicated queries its likely to end up doing things in the wrong order resulting in a very slow query - again its just not possible to tell without an execution plan.
• In particular the use of Freetext means that the full text search engine is being used, which may be causing SQL server additional problems in predicting the number of rows returned.

Really, get an execution plan.

Update:

Possible causes

In the absence of an execution plan I think that the most likely cause of the slow execution is poor estimates for the conditions on ZipCode and Description:

• Its difficult to estimate the number of matches on the ZipCode condition as its result depends on a stored procedure.
• Its difficult to estimate the number of matches on the FreeText condition as its based on results from the full-text query engine.

What I believe is happening is that SQL server is under-estimating the number of rows that will remain after filtering, and applying the queries in the wrong order. The result is that it ends up doing tens (possibly hundreds) of thousands of lookups, which is far far slower than just doing a table scan.

For a particularly complicated query I've seen SQL server perform ~3,000,000 lookups attempting to return a single row - the table didn't even have 3,000,000 rows!

Things to try - Put ZipCodeForRadius into a temp table.

If I'm right, then to help with the first one you could try putting the results of the ZipCodesForRadius stored procedure into a temporary table, I have to admit I don't have a good explanation as to why this will help, but I do have a few theories on why it could help:

• Better statistics on the temporary table
• It will have the side effect of causing the main SELECT statement to be recompiled every time you run the query (unless the range of ZIP codes is very small) - at the proc takes a few seconds anyway this will be a good thing if there is great variation in the matching zip codes. If not then there are ways of preventing the recompilation.

It certainly shouldn't do too much damage in any case.