The SQL Optimizer uses Statistics (histograms of data distribution) to decide between a Scan or a Seek. If stats are stale, SQL makes bad decisions.
The Fix: Regularly run UPDATE STATISTICS MyTable. If you just performed a massive data import, this is more important than rebuilding indexes to maintain performance.

