One test I would add: release two requests with the same key at the same instant. A check-then-create path can let both workers see an empty record, even though a later sequential retry works.

I would claim the key atomically before the side effect, bind it to the operation and payload, and give the second worker an explicit in-progress result. A crash after the external effect still needs your reconciliation state; the database claim alone cannot settle that outcome.

How do you handle recovery after the provider retention window expires? I would avoid reusing an expired key as proof that the original action never happened.