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.
Want to block all mail from any domain name that's hosted by Cloudflare? That's simple enough (and doesn't require taking a shower afterwards, unlike when writing Perl).
Just grab the plain-text version of the file that contains the list of Cloudflare's IP address ranges [0], create a CIDR table [1] containing those ranges (followed by a "REJECT"), and add an instance of "check_sender_a_access" to your "smtpd_sender_restrictions" [2].
(Bonus points for taking a couple of minutes to write a shell script that runs once per day from cron, grabs the latest version of this text file, adds " REJECT" to the end of each line for you, and triggers a reload of Postfix if there were any changes to the IP ranges that it needs to know about.)
[0]: https://www.cloudflare.com/ips-v4
[1]: http://www.postfix.org/cidr_table.5.html
[2]: http://www.postfix.org/postconf.5.html#smtpd_sender_restrict...