Getting Index Scan instead of a possible Index Seek?
You use a nonequality predicate so your "seek" operations are in fact scans which just start from some value (not from "first") and then go to the end of the clustered index leaf level.

In the other hand you return only one column which is the clustered index key so using any of indexes won't get any key lookup operations. The optimizer has to estimate what would be cheaper: scanning a nonclustered index (two int columns on the leaf level) or part scanning of your clustered index (all columns on the leaf level).

It estimates it depending on current statistics (how many rows) and metadata (what is one row size). We saw the optimizer made a mistake on &gt;20,000 predicate.


  When faced with huge amounts of data and/or when it returns more than
  50% of the data set, the query optimizer will favor an index scan.


That is a fact when the optimizer has to choose performing clustered index or table scan versus nonclustered index seek + key lookups.

In your case if your index on CustomerID were nonclustered you would always see a seek operation on that index, but if you then added another column to your output you would see the index seek + RID lookups on short resultsets and table scan on the big ones.