The approach I've been considering for quite some time is to focus less on the
bad guys than the
good guys.
Any given user, and often large groups of users (a company or organization) are going to have traffic patterns which strongly favor a small number of other hubs (mailservers), in general. That's going to be, generally, high-reputation and high-value traffic. You want to ensure that it gets through. That solves most of your problem right there.
Some of those sources are also spammers or low-value -- email marketing and the like.
Everything else is, well, everything else. Might be spam, might not. But as a first pass it tends to be less valuable. Which means you've got an immediate and low-cost option: deny first delivery on a nonpermanent basis.
If it's a well-behaved system, the delivery system will-retry the transmission in about 4 minutes. If it's a spammer, odds are that it will simply bail on delivery, or fail to honor the usual retry fall-back schedule. In the first case, problem solved, in the second, you've now got an additional datapoint for the source: it fails to adhere to conventions.
All of this is happening largely at the host-to-host level, not individual senders, so that you're both getting a large level of aggregation (a new user or service transmitting through a known host isn't a blank slate, you've already got a delivery history), and the overhead is smaller.
Yes, there are also reputation and other systems (IronPort / Senderbase, now part of Cisco, for example, as well as the DNSBLs), many of which are accessible via DNS queries, though the cost of those queries for a busy system is itself considerable (you probably want to cache results, fortunately, DNS allows for that).
And all of that logic can be rolled up pretty readily within an MTA. That's one of the powers of free software: aggregating brains and experience.