You're probably thinking - "Well what about JC Penny. They got penalized for buying links after the NYT article came out with proof of link buying". Did they get penalized? Or did those links just get devalued which resulted in a drop in rankings? Or did Google take action on them just to set an example and scare webmasters? Personally, I think the links were just devalued or JCP was given a temporary "penalty" to appease those that were calling foul. JCP has regained a lot of rankings for keywords that have the same manipulative link building patterns as what they were originally "penalized" for - look at the search results for "personalized jewelry" and you'll see JCP at #1. Look at the backlinks using OpenSiteExplorer and you'll see exactly what I'm talking about.
So what can Google do to detect "link buying" or other forms of manipulative link building? Since they can't police transactions that's out of the question. Something they can do, however, is look at the anchor text distribution of incoming links. If a website has 1000 links pointing to their site using the anchor text "my competitive keyword" and only a few other links using different anchor text, then that's a good sign there's something fishy is going on. Maybe that could signal a manual review is needed to determine if the site in question is actually relevant to the search results for that query. After all, if the searchers are happy then Google should be happy. Searchers don't know if a website is "cheating". All they know is if what they searched for is relevant to their query.