> Then most of your statuses are Complete and finding an ever decreasing percentage of Incomplete rows will result in essentially a table-scan

This is absolutely not true. Performance of your lookups will depend on the total number of "pending" items and never on the table size.

Generally indexes on boolean columns are useless due to low cardinality, but in this specific example they'll work just fine. If you have a 100 "pending" items in a table with billions of rows, search on "pending" status will never trigger a fullscan, only a 100 lookups. You can even make your index partial, so essentially your index will be your mini-queue.

Idempotency is a valid point, but it is as hard with queues as it is with databases. Exactly-once delivery is generally not possible in distributed systems (in the real world at least, where you don't own every node). Queues won't magically solve it for you, they need to implement the same locking mechanisms as the database.

Partially this is why AWS SQS boasts to be almost infinitely scaleable, but limits you at 300 (!) rps for FIFO queues.