Database has been live for 2 years now. Increase in workload is consistent. The problem started months ago, but only recently can I pinpoint what causes the problem...

Thanks Gail. STATS_DATE shows that the statistics for all indexes were last updated a couple of days ago. They were updated because when I rebuilt indexes I did...