I'm having problems with SQL Server 2000 query optimizer not using non-clustered indexes when performing a simple query where the result set is larger than a few thousand rows out of a table of 500,000... if the results set is maybe 5000 rows or less, it uses an Index Seek perfectly, but cross the threshold where it reverts to a table scan and it takes forever.

Any ideas would be great. I've gone through 3 SQL Server support people and tried several of their workaround suggestions.