The only solution I found was to put a 15 minute delay on all incoming email from a cloudflare domain, then do a second check of the blacklists. This solved the problem, as the sending ips (not cloudflare) tended to get blacklisted within 15 minutes.
In my mind if you're hiding people's websites behind your "cloud", you have a responsibility to kick off the spammers.
There are also several other (seemingly lesser known) restrictions available, such as "check_sender_a_access", "check_client_mx_access", and "check_helo_ns_access" (plus similar variations you can likely think of) that you can use to take action based upon things like the IP address(es) listed in the A RR for the client MTA's hostname, the hostname(s) listed in the MX RRs for the client MTA's IP address, and/or the authoritative DNS servers of the domain name provided by the client MTA during the HELO/EHLO phase.
Imagine a spammer that had hundreds of domain names, all of which used her own DNS servers, jack.ns.example.com and jill.ns.example.com. Using check_sender_ns_access, for example, you can quickly and easily reject all mail where the domain name in the envelope from address uses one of these authoritative DNS servers.
If you get creative, you can come up with some really effective combinations that are actually pretty simple.