Vou responder minha própria pergunta, pois foi difícil encontrar a resposta correta e fui apontado para o problema pela saída do SQL Server 2012 Execution Plan. Como você vê na pergunta original - tudo parece bem na superfície. Este é o SQL Server 2008.
Quando executo a mesma consulta em 2012, recebi um aviso em
CHARINDEX consulta. O problema é - o SQL Server teve que fazer a conversão de tipo. Address1 é VarChar e a consulta tem N'1124' que é Unicode ou NVarChar . Se eu alterar esta consulta assim:SELECT *
FROM LOCAddress
WHERE (CAST(CHARINDEX(LOWER('1124'), LOWER([Address1])) AS int))
Em seguida, ele é executado da mesma forma que
LIKE consulta. Portanto, a conversão de tipo causada pelo gerador do Entity Framework estava causando esse impacto horrível no desempenho. 
