But you have a fairly major problem with all these solutions and that is when a message leaves a queue. For a message queue you want it to leave the queue when delivered. For a job queue you want it to leave the queue when the work is completed but not to be sent out in the mean time. Now imagine you have processing jobs that take two weeks with 16 cores to complete.

That's one thing that makes this a hard problem. If you have open transactions for two weeks "Deleting this...." then autovacuum is going to be totally ineffective. So failure detection and recovery is an important (and probably the hardest) part of the problem.

PgQ looks to me like it is a solution to a message queue problem not a work queue problem.