So I just got finished with a Friday afternoon head scratcher (that luckily had a resolution).
Looking at the XML execution plan, we see that the "seek" query has values designated for ParameterCompiledValue and ParameterRuntimeValue. The "scan" just shows a value for runtime.
We experiment with RECOMPILE and OPTIMIZE FOR query hints. No luck.
I then look at the index scan operator and notice that there is an implicit data type conversion going on. The index seek, on the other hand, does not do an implicit data type conversion.
We look at the base table - and the column referenced in the predicate is varchar(24). We look at the local variable data type - and it is defined as Unicode - nvarchar(24). We change it to match the table - and now we're happily doing index seeks.
More confirmation that implicit data type conversion, in addition to silently eating up extra CPU, also can generate unnecessary I/O (not to mention 7 minutes of support time).