From this research paper on SNARE, I present this nugget:
For ham, 90% of the messages travel about 4,000 km or less. On the other hand, for spam, only 28% of messages stay within this range.
My personal observations mirror yours and note that even now in 2014, geographic location continues to be an excellent predictor of spam. As others pointed out, GeoIP location (country or distance) alone is not a sufficiently reliable basis for blocking connections. However, combining GeoIP distance with a few other pieces of data about the connection, such as FCrDNS, HELO hostname validity, sender OS (via p0f), and SPF provides a 99.99% reliable basis (as in, a .01% chance of a FP) for rejecting 80% of connections before the DATA phase.
Unlike some SMTP tests (such as a DNSBL listing in zen.spamhaus.org) which have very low FP rates, none of the aforementioned tests individually are a sufficient basis for rejecting connections. Here's another pattern that falls into that category–-the envelope sender user matches the envelope recipient user. I've noticed that about 30% of spam follows this pattern: from: email@example.com to: firstname.lastname@example.org. It happens far more frequently in spam than in valid mail flows. Another spammer pattern is a non-matching envelope and header from domain.
By heuristically scoring these "spam appearing" characteristics, the basis for an extremely reliable filtering system can be assembled. SpamAssassin already does (or can do) most of what I described. But you also asked for a solution that would handle sufficient load and scale well. While SpamAssassin is great, I didn't see "massively reduced resource consumption" anywhere in the 3.4 release notes.
All the tests I listed in the first paragraph occur before SMTP DATA. Combining those early tests forms a sufficient basis for rejecting spammy connections before SMTP DATA without any False Positives. Rejecting the connection before SMTP data avoids the bandwidth costs of transferring the message as well as the heavier CPU and network load of content based filters (SpamAssassin, dspam, header validation, DKIM, URIBL, antivirus, DMARC, etc.) for the vast majority of connections. Doing far less work per connection scales much better.
For the smaller subset of messages that are indeterminate at SMTP DATA, the connection is allowed to proceed and I score the message with results from the content filters.
To accomplish all I have described, I've done a bit of hacking on a node.js based SMTP server called Haraka. It scales very, very well. I have written a custom plugin called Karma which does the heuristics scoring, and I've put all the weighting scores into a config file. To get an idea of how karma works, have a look at the karma.ini config file. I've been running karma in production for a few months and I'm getting "better than gmail" filtering results. I'm working with the Haraka authors to get this updated version of karma merged it into the main repo.
Having a look at the tests run by the FCrDNS, helo.checks, and data.headers plugins in my repo. They might provide you with additional filtering ideas. If you have further ideas for reliably detecting spam with cheap (pre-DATA) tests, I'm interested to hear them.