SQL Server 2005 - Row

ORDER BY em ROW_NUMBER cláusula não garante a ordem do conjunto de resultados.

ROW_NUMBER geralmente usa classificação no plano de consulta, o que resulta no fato de os valores serem pré-ordenados.

Este é um efeito colateral e não deve ser invocado.

DISTINCT usa Hash Match (Aggregate) que quebra a classificação.

Adicionar ORDER BY cláusula ao final da consulta:

SELECT  DISTINCT (ID), State_Id, Name_Of_Trip, Date_Of_Travel, Creation_Date, Locking_Id, Applicant_Name, Reference_Number, State_Name
FROM    (
        SELECT  app.ID, app.State_Id, app.Name_Of_Trip, app.Date_Of_Travel,
                app.Creation_Date, app.Locking_Id, app.Applicant_Name, app.Reference_Number, 
                State.Name AS State_Name, ROW_NUMBER() OVER(ORDER BY Reference_Number DESC) as rowNum  
        FROM    Application_Leg AS app 
        INNER JOIN
                State AS state 
        ON      app.State_Id = state.ID
        WHERE   app.State_Id IN (5, 6, 8)
                AND app.Organisation_Id = 12 
                AND Leg_Number IN
                (
                SELECT  Leg_Number 
                FROM    Application_Leg as al
                INNER JOIN
                        Organisation as org
                ON      al.Organisation_Id = org.ID
                WHERE   al.ID = app.ID
                        AND org.Approval_Required = 1
                        AND Mode_Of_Transport = 1
                )
        ) AS pagedApplications
WHERE   rowNum BETWEEN 0 AND (0 + 10)
ORDER BY
        ReferenceNumber DESC

Observe também que ele não retornará 10 resultados distintos, ele retornará DISTINCT dos primeiros 10 resultados.

Se você quiser o primeiro, use este:

SELECT  DISTINCT TOP 10 ID, State_Id, Name_Of_Trip, Date_Of_Travel, Creation_Date, Locking_Id, Applicant_Name, Reference_Number, State_Name
FROM    (
        SELECT  app.ID, app.State_Id, app.Name_Of_Trip, app.Date_Of_Travel,
                app.Creation_Date, app.Locking_Id, app.Applicant_Name, app.Reference_Number, 
                State.Name AS State_Name
        FROM    Application_Leg AS app 
        INNER JOIN
                State AS state 
        ON      app.State_Id = state.ID
        WHERE   app.State_Id IN (5, 6, 8)
                AND app.Organisation_Id = 12 
                AND EXISTS
                (
                SELECT  Leg_Number 
                FROM    Application_Leg AS al
                INNER JOIN
                        Organisation as org
                ON      al.Organisation_Id = org.ID
                WHERE   al.ID = app.ID
                        AND al.LegNumber = app.LegNumber
                        AND org.Approval_Required = 1
                        AND Mode_Of_Transport = 1
                )
        ) AS pagedApplications
ORDER BY
        ReferenceNumber DESC

SQL Server 2005 - Row_Number()