Земечено "слетание" статистики при удалении данных в таблице. Похоже, что распределение данных в статистике при удалении строк из таблицы становится совсем неверным. Именно поэтому в стандартные процедуры обслуживания SQL включаю пересбор статистики по всем таблицам ночью. На всех перечисленных Вами таблицах нам пришлось добавлять свои индексы SpeedUpIdx
