Now if you have a race condition between the query of $q->pending and $q->dequeue (another threads empties the queue in between) you can get a block.

Try $q->dequeue_nb instead.

(Disclaimer: I have no experience with threads, so don't be surprised if that's not the problem...)