What they should do instead is this:
1. If the server is not overloaded, do not captcha any traffic at all
2. If the server starts being overloaded, only captcha traffic from IPs that have been detected as attacking THAT specific site
3. If the server is still overwhelmed, only then switch to captchaing all IPs with "bad reputation"
Most websites are probably almost never under attack, so this would make encountering CloudFlare captcha extremely rare in the wild while still providing DDOS protection.
They could even only do this for Tor exit nodes and other IPs that are known to be used by lots of people.
If a site is being DDOSsed a lot and the slower start up of this technique is a problem, then they can revert for those sites to the current behavior of using reputation.