TSQL проверява дали съществува конкретна последователност от редове

Мисля, че това може да се реши с помощта на рекурсивен CTE:

with change_tree as 
(
  SELECT order_id,
         previous_status_id, 
         next_status_id,
         cast(next_status_id as varchar(max)) as status_path
  FROM status_change
  WHERE previous_status_id = 1
    AND order_id = 2

  UNION ALL 

  SELECT sc.order_id,
         sc.previous_status_id,
         sc.next_status_id,
         ct.status_path + ',' + cast(sc.next_status_id as varchar(max))
  FROM status_change sc 
    JOIN change_tree ct ON ct.next_status_id = sc.previous_status_id AND ct.order_id = sc.order_id
)
SELECT *
FROM change_tree
WHERE status_path = '2,3,5';

Това, което по същество прави, е (рекурсивно) да свърже всички стойности на next_status_id в един низ, с който можете да сравните.

От вашите примерни данни не ми е ясно кой ред маркира "началото" на хронологията на промените в състоянието на поръчката. Ще трябва да коригирате къде в първата част на обединението, за да изберете правилния "начален" ред.