Database table as a queue, order by another table's column
It seems that preventing the locking of candidate rows is impossible with an ordering on a column not part of the clustered index.
I came up with a workaround, that seems to solve the problem on the minimal example i provided. I'll do some tests to make sure if it solves the actual production problem.
The idea is to split dequeue operation into two steps. First step respects the ordering and selects a small candidate set; second step ignores any orderings and works on this small set. Thus preventing locking of all the rows.

Select more than one rows to be dequeued, without removing the original order by clause. In my case, i changed the CTE to select top(50) rows. And also changed (ROWLOCK, READPAST, UPDLOCK) to read (NOLOCK) as i don't intend to dequeue all these rows, these are all just candidates for the one row i am willing to dqueue. These rows are stored in a table variable, to be joined in the second step, which follows below.

Create a new (second) CTE, this time joining with the table variable (which contains at most 50 rows), where clauses will be repeated here to prevent an unwanted row appearing in the result set. The ordering this time is removed from the new CTE to prevent the locking.


Although not critical for my specific needs, there are a couple of issues with this approach:

If more than 50 users simultaneously try to dequeue, only the lucky 50 of them will succeed, while others will not be able to get an item.
Granularity of the ordering is lost, each item in the candidate list of 50 are treated equally.
Again on the ordering, it might be the case that a user dequeues an item which was not in the top 50, but this won't be a totally off target miss; it will be close to the top 50. This is due to the two step approach: things might change and new items might arrive that have higher priority, from the time first CTE runs until the second CTE which performs the actual update. Anyways, it is highly likely that the item dequeued is within the first 50 items.

Test script for the new approach is as follows:
BEGIN TRAN TRAN1
DECLARE @QUEUEID INT;

DECLARE @CANDIDATE_TABLE TABLE (
    QUEUEID INT NOT NULL
);

;WITH CANDIDATE_CTE AS 
(
    SELECT   TOP(50) Q.QUEUEID
    FROM     DBO.QUEUE Q WITH (NOLOCK)
    JOIN     DBO.QUEUE_ORDERING QR WITH (NOLOCK) 
    ON       QR.QUEUEID = Q.QUEUEID
    ORDER BY QR.ORDERING_COLUMN DESC
)
INSERT INTO @CANDIDATE_TABLE (QUEUEID)
SELECT QUEUEID FROM CANDIDATE_CTE;

;WITH QUEUE_CTE AS
(
    SELECT   TOP(1) Q.QUEUEID
    FROM     DBO.QUEUE Q WITH (ROWLOCK, READPAST, UPDLOCK)
    JOIN     @CANDIDATE_TABLE CT
    ON       CT.QUEUEID = Q.QUEUEID
)
SELECT @QUEUEID = QUEUEID FROM QUEUE_CTE
PRINT 'processing item # ' + CAST(@QUEUEID AS VARCHAR) 

WAITFOR DELAY '00:00:05' 
COMMIT

The outputs of two simultaneous sessions are:

(10 row(s) affected)
processing item # 10



(10 row(s) affected)
processing item # 9