Victor,
I had a similar problem (on a MUCH smaller table) and the Query Analyzer said the Query was optimized, but I also saw it took a very different route for the slow query than for similar fast queries. So I forced the order of search on the slow query and it cut the time by 99% (yup, 1/100 of the original time).

HTH
Barbara

>Did that already. I checked the performance on the query - even on the queries that take up to 3 minutes SQL Server informs me that it is as optimized as possible and the only other way to improve performance is by creating a clustered index. The problem with that is that it only allows one per table and with all the different combinations that people can search a clustered index won't help. At least I don't think it will - will it???