ORDER BY and WITH(ROWLOCK, UPDLOCK, READPAST)

I need to set up a queue system using some SQL tables, like the one described here. That being, and since I need to filter queued items by different critera, inside a stored procedure I am using

BEGIN TRANSACTION

CREATE TABLE #Temp (ID INT, SOMEFIELD INT)

INSERT INTO #Temp SELECT TOP (@Something) TableA.ID, TableB.SomeField FROM TableA WITH (ROWLOCK, READPAST) INNER JOIN TableB WITH (UPDLOCK, READPAST) WHERE Condition1

INSERT INTO #Temp SELECT TOP (@Something) TableA.ID, TableB.SomeField FROM TableA WITH (ROWLOCK, READPAST) INNER JOIN TableB WITH (UPDLOCK, READPAST) WHERE Condition2

(...)

UPDATE TableB SET SomeField = 1 FROM TableB WITH (ROWLOCK, READPAST) WHERE ID IN (SELECT ID FROM #Temp)

COMMIT TRANSACTION

I am using ROWLOCK in the first table and UPDLOCK in the second because, after this select, I am going to update TableB only, though I need to make sure that these lines don't get updated inTableA by any other concurrent query. Everything goes well until the point where I need to insert an ORDER BY clause in any of the SELECTs above, so that only very specific IDs get selected (I must really do this). What happens is:

1) Without ORDER BY, two concurrent executions execute as desired, returning different and non-overlapping results; however, they don't return the results I want because those precise results were outside the scope of every SELECT statement.

2) Using ORDER BY and two concurrent executions, only the first one returns results. The second one does not return anything.

I recall seeing on a blog that for these kind of queries with WITH (ROWLOCK, READPAST) and ORDER BY to work one needs to create indexes on the fields one is using in the ordering. I tried it, but I got the same results. How can I get past this problem?

Edit: For example, if I have a table TestTable with fields (TestID INT, Value INT) and values "(1,1), (2,2), ..." and execute "simultaneously"

BEGIN TRANSACTION

SELECT TOP 2 TestID FROM TestTable WITH (UPDLOCK, READPAST)

WAITFOR DELAY '00:00:05'

COMMIT TRANSACTION

the first execution returns lines (1,2) and the second one returns (3,4) as espected. However, if I execute

BEGIN TRANSACTION

SELECT TOP 2 TestID FROM TestTable WITH (UPDLOCK, READPAST) ORDER BY VALUE ASC

WAITFOR DELAY '00:00:05'

COMMIT TRANSACTION

the first one returns (1, 2) and the second returns nothing. Why is this?!

As expected

The SELECT with the ORDER BY, without ROWLOCK, without index will have a table lock because of a scan/intermediate sort to work out TOP 2. So the 2nd session skips the whole table because of READPAST
The SELECT without the ORDER BY is just picking any 2 rows, which happen to be in order of insert (pure coincidence, there is no implied order). The fact that these 2 rows are locked causes the 2nd session to skip to the next non-locked rows.

SQL Server attempts to keep locks as granular as possible but the scan means a table lock. Now, this wouldn't normally make a difference (it'd be a shared read lock) but you have UPDLOCK too which means an exclusively locked table

So, you need both of these

3 hints in the SELECT queries (ROWLOCK, UPDLOCK, READPAST) to control granularity, isolation and concurrency.
Using ROWLOCK only will still cause an exclusive lock on every row to scan/sort.
an index on Value INCLUDE TestID to make the SELECT efficient. An index only will probably fix the concurrency but it won't be guaranteed.

In one of your previous questions I linked to my answer (in a comment) to SQL Server Process Queue Race Condition where I have all 3 lock hints