Yikes.. interesting to find two sentences that seem to be at odds with each appearing next to each other!
It seems you’ve never heard of domain redemption/recovery/restoration fee before, so let me explain.
This is a fee charged by the TLD registry operator. As a result, you’ll pay a fee to restore a domain that’s gone into redemptionPeriod
irrespective of which registrar you use.
But, just as every other registrar makes money from domain registrations, they also markup the redemption fee… sometimes A LOT.
For instance, NameCheap charges $94.98 for your TLD (ref), Bluehost charges $99.95 (ref), and eNom charges a whopping $250 (ref).
How do these compare to the $40 that Cloudflare asked you to pay (which is probably the actual fee they have to pay to the registry operator with no markup)?
I’m sorry for your loss.
But note that Registrars (like Cloudflare) don’t control when a domain is released to the public. It’s the registry operator that releases the domain… and, even then, they follow a strict domain life-cycle timeline.
Cloudflare could not have prevented the release of your domain after it’s gone the full 75 days (more or less, depending on TLD) following the domain’s expiration.
Again, I’m sorry for your loss, and I’ve made my own noise about Cloudflare’s on-going billing and support nightmares elsewhere already.
But my goal here is for you to understand the norms and processes with domain management… so that, going forward, you don’t have the false hope of expecting your registrar (any registrar!) to do things that they have no control over – like waiving the restoration fee, or holding a domain beyond the last pendingDelete
date.

Domains are paid for a period of 1 year (or multiples thereof). This is the only period when registrants have full legal ownership of the domain. Any extensions beyond this is considered a “grace period”.
After the domain’s registration is revoked and expunged from the TLD’s registry (by the registry operator, not the registrar, and following the pendingDelete
period), the previous registrant cannot exert any ownership claim to those strings of characters any longer (except for things like trademarks etc). The domain is as good as if it was never registered before… and anyone is free to register it. And there’s a whole industry of “domainers” doing just that.
As the domain has already been registered by someone else, there’s not a whole lot you or your registrar can do to re-claim it… except to buy it from the current owner (or, if you have a registered trademark and a lot of money to pay lawyers, pursue reclamation in the courts or through ICANN’s UDRP process).
Good luck!