>You may want to start reading from this article
>Parameter Sniffing
>
>and then proceed with this article
>http://www.sommarskog.se/query-plan-mysteries.html

I read the first article and applied some of that. The OPTION RECOMPILE completely destroyed the execution plan. Now, it doesn't want to use the index and falls in the lookup mode. Then, I tried the OPTIMIZE FOR approach and it forced it to use the index, but only one one server, which means that the same database setup on two servers may not react the same in the execution plan based on what was executed before.

I will read the second article now.