Synchronizing queues and databases is difficult to impossible.  It's possible that a message consumer subscribes after a message for a task has been delivered to the exchange, but before it's in the database, so just polling at consumer startup isn't enough.  It's also possible that a message is delayed, so consumers shouldn't assume that any messages they receive indicate up-to-date state about the database (so, for example, a message may arrive about a pending task that is, in fact, already claimed by another worker).

I've been struggling with this problem in Buildbot, as well.  I'd *love* to learn that there's a solution that doesn't involve either re-implementing the DB/MQ layers, or using a single product that can do both (e.g., Redis, which has other issues).

I think the general approach here is correct, though: treat messages as advisory ("there *may* be a pending task right now") and the database as authoritative.  That allows polling to be relatively infrequent (on the scale of minutes), but it's still required.