For something like this service, simple rate limiting per IP / netblock, along with TCP/IP fingerprinting for VPN endpoints and such, could be very effective.

I run histograms for connections per netblock on my email servers, and even removing only the most egregious attempts at abuse almost empties my logs.

On the other hand, Cloudflare has issues with tons of less popular networks, with VPNs, with less affluent countries, with non-mainstream OSes and browsers, et cetera, all of which ends up punishing many people in ways that are completely disproportionate to the amount of abuse avoided.

It reminds me of the quote from fortune(6):

As far as we know, our computer has never had an undetected error. -- Weisert

You don't know how many people Cloudflare has marginalized because you don't see their visits.