SQL Server 2005 - Número

ORDER BY en ROW_NUMBER cláusula no garantiza el orden del conjunto de resultados.

ROW_NUMBER por lo general, utiliza la ordenación en el plan de consulta, lo que da como resultado que los valores salgan preordenados.

Este es un efecto secundario y no se debe confiar en él.

DISTINCT utiliza Hash Match (Aggregate) lo que interrumpe la clasificación.

Agregar ORDER BY cláusula al final de la 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

También tenga en cuenta que no devolverá 10 resultados distintos, devolverá DISTINCT de los primeros 10 resultados.

Si quieres lo primero, usa esto:

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 - Número_fila()