Should I use a partial index on a queue table where I only ever scan 'pending' rows?
Yes — this is the textbook use for a partial index. WHERE status='pending' indexes only a few thousand rows; small, cache-friendly, skips the millions of dead ones. Include the ORDER BY column and pair it with SKIP LOCKED.