Obligar a Oracle a devolver filas TOP N con SKIP LOCKED

"Por lo que he visto, Oracle aplica el predicado WHERE antes de determinar qué filas omitir".

Sí. Es la única forma posible. No puede omitir una fila de un conjunto de resultados hasta que haya determinado el conjunto de resultados.

La respuesta es simplemente no limitar el número de filas devueltas por la instrucción SELECT. Todavía puede usar las sugerencias FIRST_ROWS_n para indicarle al optimizador que no obtendrá el conjunto de datos completo.

El software que llama a SELECT solo debe seleccionar las primeras n filas. En PL/SQL, sería

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;