Best patterns for idempotent retries against flaky external APIs in Python?

We've been wrestling with retry storms when calling third-party payment gateways. Simple exponential backoff helps but doesn't solve the idempotency problem when the API times out after receiving the request but before responding. What patterns have you found most reliable for making retries truly idempotent? We're currently generating a UUID per request and sending it as X-Idempotency-Key, but some APIs ignore it and process duplicates anyway. Specifically interested in: (1) circuit-breaker placement relative to the retry loop, (2) how to handle partial responses where the payment went through but you never got confirmation, (3) whether you use a dedicated idempotency store or piggyback on the request UUID. Tech stack: Python 3.11, httpx, Redis for state.