PgQ, part of Skype's SkyTools package, is a good example of queues in Postgres. It's used by their Londiste, a replication tool that was developed before built-in replication was mature.
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.
If I understand you correctly, this handles your work queue case.
In my experience you have several critical issues:
1. What happens when a job silently fails?
2. What happens when a job takes a lot longer than expected to succeed?
If you solve the first with a timeout, the second leads to a job rerun. The best (only?) solution I have found is to have some awareness in the job queue of the fact that the job is currently being processed. In my previous work we used advisory locks for that.
Given your critiques of everything else out there (from what I gather from the rest of your comments in this thread), it seems like your identified a possible business opportunity.
What happens if someone trips over a power cord after a week of this job running? How do you detect and recover? What if, due to the size of data passed in, the job takes a week longer than expected?
This is why you cannot always reduce a work queue to a message queue.