>You are right. But is is hard to have a good benchmark since different customers has different number of records. My guess is that the total number of records (on average) matching the WHERE will not be more than 2000. On my PC, when I run these queries, both cases (with about 1000 records) are almost instantaneous.

You are facing a similar situation I have here on the Universal Thread. On my account, sometimes, because I have so many replies, the way the SQL Server index works, sometimes forces me to reindex just so to keep it clean and avoid a 2-second delay, where usually, I have it in 0.1 second. I haven't found any explanation for it so far. But, it only happens on my account. It may be ok for months and then, it happens. Everything is optimized. I also makes use of advanced SQL Server indexing but this is a weird situation.