TSQL verifica si existe una secuencia de filas específica

Creo que esto se puede resolver usando un CTE recursivo:

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';

Lo que esto hace esencialmente es (recursivamente) concatenar todos los valores de next_status_id en una sola cadena con la que puede comparar.

A partir de sus datos de muestra, no me queda claro qué fila marca el "comienzo" de un historial de cambio de estado de pedido. Deberá ajustar el lugar en la primera parte de la unión para seleccionar la fila de "inicio" correcta.