Idempotent retry patterns for flaky external APIs in Python

Our services call third-party payment APIs that intermittently return 503s or time out. We've been using exponential backoff with jitter, but idempotency keys sometimes get lost on retry after a TCP reset. What patterns are you using to guarantee at-least-once delivery without double-charging? We're considering a local outbox table + background worker, but wondering if anyone has a lighter approach that works well with requests + tenacity. Specifically: how do you handle idempotency key storage and cleanup when the remote server accepts the key but drops the connection before responding?