Earlier this year I bent over and took one from the Cutts mafia and started cleaning-up the links. After 3 months of horrible work the client then got hit with a manual penalty = 40% down in Google traffic = client very pissed and me stressed. I wrote the letter to the spam team and supplied the evidence (which was genuine), felt unclean for a while, and in two weeks got the manual penalty removed.
I have continued cleaning the back-links, though I think I'll leave it for now, and dreaming-up other ways of promoting the site. We have also worked hard on the site itself.
Rankings are starting to improve - I have a lot of green arrows in the Avg Position column in GWT today. This is for a local biz / e-commerce store with branded competition with deep pockets.
Matt Cutts, there is a part of me that hates your guts (the same part of me that hates doing aerobic training), but you are also opening-up a whole new raft of opportunity. Plus there are fewer people around now that offer 'SEO services' (whatever that means). You're also making all those Asian guys that could win with brute force + low cost almost irrelevant. So for that - cheers.