>>My guess is that the index statistic became inaccurate. You may want to run UPDATE STATISTICS ... WITH FULLSCAN for that index periodically.
>
>I thought SQL Server was bullet proof in regards to that. I wouldn't want to start establishing procedures like this just so to make sure everything is always up to date. There must be something that caused this.

The Remarks section of the UPDATE STATISTICS (Transact-SQL) BOL 2008 topic list conditions under which Index/Column statistics may become inaccurate:

- If there is significant change in the key values in the index, rerun UPDATE STATISTICS on that index.
- If lots of data in an indexed column has been added, changed, or removed (that is, if the distribution of key values has changed), or the table has been truncated by using the TRUNCATE TABLE statement and then repopulated, use UPDATE STATISTICS.