Index definitions?

Has the total number of rows in the table changed since this worked properly?

Are your indexes fragmented? Are the statistics out of date?

I'm not asking just to be a pain. I'm asking because I want as clear a picture of the problem as possible.