Из MSDN:

Перед выполнением кэшированного плана запроса компонент Компонент Database Engine проверяет, ссылается ли план запроса на актуальную статистику.

Вопрос. Что он делает если она устаревшая? 
Помечает план как TRIVIAL или обновляет статистику?

Выполнение запроса и сбор статистики - два разных, не зависимых друг от друга процесса. Сбор статистики производится тогда, когда ему положено проводиться. Алгоритм определения этого момента, описан в MSDN и не зависит от того, обращается ли таблицам какой-либо запрос. Когда же выполняется запрос, план которого кэширован, определяется, актуальна ли статистика для этого плана и если окажется, что статистика с учетом которой строился кэшированный план обновлена, строится новыый план.