>>So, what plans did you get when you tried both suggestions? Can you post them here?
>
>I haven't change anything. Because this index is constantly being changed, it seems this can corrupt the index from time to time. So, I only executed the reindex on that index today and that resolves the issue. I will check it on an occasional basis. Maybe this was caused by a one timer or else. So, we'll see.

Too bad - I was interested in the execution plans and the speed test difference. Can you at least run both statements in SSMS and check actual execution plans to see if distribution is equal (50/50) or not?