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