[jeffbee]

It doesn't need to be computationally costly because, as you seem to imply, there are tiers of cost tradeoffs. You can invoke a very cheap classifier at SMTP time, that is biased to have few false positives, that will temporarily reject all that which is highly likely to be spam. You can do this without even glancing at the body. Of course, having signals about peer reputation is the strong suit of Gmail or Microsoft, and the distributed, open community would need to solve the problem of promptly updating and distributing such reputation signals. And by "promptly" I mean within seconds of the leading edge of an attack.

Then there are increasing tiers of cost that you would only run after it becomes likely that the message is acceptable. As you say, you would only run an antivirus on a message on the verge of delivery, because decoding the attachment and running the AV (in an expensive sandbox) is so costly.