This exactly where I observe MSSQL dropping to table scans too soon. If indexes are cached (or when using a ssd), they will be much faster for many many records than a table scan (which will always require disk access in a realistic scenario).
I agree that table scan will be faster if I need a large percentage of the table (more than can be cached).
So I take it you are not using any kind of cache in your memory hierarchy?