Necroing this question but there's an explanation that no-one seems to have considered.
STATISTICS - Statistics are not available or misleading
If all of the following are true:
Then sql server may be incorrectly assuming that the columns are uncorrelated, leading to lower than expected cardinality estimates for applying both restrictions and a poor execution plan being selected. The fix in this case would be to create a statistics object linking the two columns, which is not an expensive operation.