Forçar o Oracle a retornar as linhas TOP N com SKIP LOCKED

"Pelo que vi, a Oracle aplica o predicado WHERE antes de determinar quais linhas devem ser ignoradas."

Sim. É a única maneira possível. Você não pode pular uma linha de um conjunto de resultados até determinar o conjunto de resultados.

A resposta é simplesmente não limitar o número de linhas retornadas pela instrução SELECT. Você ainda pode usar as dicas FIRST_ROWS_n para direcionar o otimizador para que você não pegue o conjunto de dados completo.

O software que chama o SELECT deve selecionar apenas as primeiras n linhas. Em PL/SQL, seria

DECLARE
  CURSOR c_1 IS  
    SELECT /*+FIRST_ROWS_1*/ qt.ID
    FROM QueueTest qt
    WHERE Locked IS NULL
    ORDER BY PRIORITY
    FOR UPDATE SKIP LOCKED;
BEGIN
  OPEN c_1;
  FETCH c_1 into ....
  IF c_1%FOUND THEN
     ...
  END IF;
  CLOSE c_1;
END;