As long as Google try to trap this exclusively algorithmically I think they'll fail.
Why not actually try some form of human intervention?
What I usually see is that spam is facilitated by networks of sites, and although I discover a network because I analysed one site, that network is being used to help hundreds of other sites. Manually taking down the network's ability to pass PR or anchor text would probably stop hundreds of sites ranking. Placing warnings (like the malware warnings) on participating sites would also send a clear message.
Where the network is traceable back to an agency (and some are) then I personally would kill their site(s) too, denounce them publicly on a Google blog, and place a warnings in the SERPs.
Spam is a huge problem, and even a fairly large dedicated human team might only be able to act on a small percentage of the reports.
But on the other hand humans can spot spam instantly - and without the 'false positives' that plague algorithmic detection.
And I think this would be far more of a deterrent. If word got around that spam reports were actually acted on by humans and manual penalties were handed out, might that not deter people more than the current situation?