More Roadblocking Ideas
You can stop these mails just as you would stop any other mails originating from nonconformant mailers. OTOH, greylisting seems to be losing its effectiveness (well, duh, of course it is). I use an absence of MX record to stop them coming to my primary account, but they still get through forwarders.
Here are a couple of other ideas ...
1. Fuzzy checksum the emails. Sure the binaries are morphing all the time, but surely all these emails have similar form? Haven't checked yet, but I'd be willing to bet Vipul's Razor can detect all major variants of these by now. Perhaps the AV industry should focus more on the vector and less on the actual payload. ClamAV has a good general-purpose scanning engine too, perhaps it could be adapted to scan vanilla plaintext emails for these telltail signs? Would be great for the milter interface - could reject the DATA outright (554 5.7.0 Go away, you f**king moronic end-luser.)
2. Internet mail is abused again. So how long is it before port 25 blocking becomes mandatory? I don't mind at all, provided that I can immediately and easily unblock myself without question. It goes without saying, of course, that the process requires authentication and can't easily be automated by a computer program, although I suspect that wouldn't be too long in the works before the VXers break that, too.