If we rebuild the indexes on the table, then all is well again but we are having to do this every day, to 'handle' the problem.

Wedo have overnight tasks to modify certain fields (not key fields) in the table.

Next time, I will check the statistics, but as the correct index is used/forced (the primary key), I'm not sure where exactly to look further.