Some badly implemented C/R schemes may not scacle, but C/R, as implemented according to my best practices, scales fine — leaving aside, for a moment the issue of what to do about challenging mail with fake addresses.

In a world where everybody used C/R, you would only get a challenge when:

1. You email somebody you have never mailed to or from before, AND
2. Your message is not clearly identified as non-spam by the recipient’s spam filters, AND
3. You don’t take any extra steps that become adopted, such as including a cpu-stamp, or signing your mail

This is something I see happening perhaps a few times a week, if the whole world used C/R. That scales fine. There is an issue when you change E-mail addresses. Then you will get a new slew of challenges, temporarily. But it’s not giant burden. In such cases I would recommend the adoption of tools to bypass all anti-spam including C/R because most spam filters do use some level of whitelisting, and you give up your whitelist privs when you change E-mails.