>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.