I very, very nearly suggested that it could be a corrupted index as well. The reason I decided not to mention it is that although I know a corrupted index is theoretically possible I had never actually seen it happen in 10 years of SQL Server usage.

Many of the larger databases I have worked with have regular jobs to rebuild indexes, I guess that is why I have never seen a corruption.