If I felt sure that ONLY fly by night spammers would find it hard to recover, I'd feel okay about Cutts' advice there. But no system is perfect. Some innocents are bound to get caught in this big web Google is casting.
I wonder if the reason Google started issuing unnatural link messages is in anticipation that if the govt ever intervenes, it might force them to start communicating to webmasters "Here is what you have done wrong. Here are things to do that will get you back in our good graces."
But of course that's problematic. What gets you back in with Google today will almost surely be considered spam someday, because Google defines spam as "anything that gets a site in good with us."