>>Could you post query execution plan for both cases?
>
>The execution plan is attached and is the same for both cases.
>
>What I did:
>
>1. I observed that it was slow
>2. I copied the script and executed it in SSMS with Execution Plan
>3. The image is attached
>4. I then reindexed
>5. I observed that it was fast
>6. I copied the script and executed it in SSMS with Execution Plan
>7. I observed that both execution plans were identical
>
>As is, it will be like that for a few hours. Then, it will start to get slow. I see Naomi as added some info. I will check on that as well.

Is your other index (the same as combo without included column) used somewhere? I'm thinking, what if you drop that index and rely on combo index always?