SQL Server - Update with Output not working in Parallel environment
While I agree that "the sp_getapplock/sp_releaseapplock approach [is] the most straight forward and least dirty way to manage explicit semaphore logic."

There is a reason that's not working and a way to fix it directly, and enable multiple, concurrent transactions to simultaneously fetch disjoint rows:

This should fix it:

UPDATE sys_QueueJob
    SET StartedOn = GETDATE()
    OUTPUT DELETED.Id as Result
    WHERE Id = (select top 1 qj.Id 
                    from sys_QueueJob qj with (rowlock, updlock, readpast)
                    where qj.ProcessedOn is null AND qj.StartedOn is null                                                   
                    order by CreatedOn asc)


See Using Tables as Queues