>>The execution plan suggests to create an index. So, I create it. Now, when I view the execution plan, I see it does not complain anymore. However, when looking at the execution plan, it does not use the index it suggested. If I remove that index, the execution plan wants it. I create it, it does not use it. What's up here?
>
>Indexes are based upon statistics. If the index is not there, the statistic is missing. Apparently adding the index lets the optimizer conclude not to use the index because the cost is too high. It could not draw that conclusion without the index because then the statistics were missing

So the optimizer wants the index so it knows it doesn't want the index.

There is something witty here to say about MSSQL being either like a cat or a woman... I can't decide.