> Shouldn't plain vacuum be enough? The space is going to be reused for new items anyway, it won't take more of the space not already reserved by the database?

In theory, yes. In practice, I've seen a lot of bloat being preserved despite using aggressive autovacuum settings. I'm guessing this is due to fragmentation?

> On another topic, do you require using a SQL database for your queue?

I'd need some way to browse the queue and select items for processing using arbitrary queries.