@menntarra - I think any action that takes you closer to G's guidelines is a positive move. Maybe the time is here for us all to be brutally honest with ourselves and conduct a sweep of our metas and content, anchor text and headings.
But I would confine your activity to on-site adjustments until the dust has settled. I have recently received a request from a webmaster to remove a link I had to his site, a perfectly legitimate organic link. It turns out that his site had dropped from the serps and he'd put in a reconsideration request. Google had then sent him an email stating that he was still in violation and suggesting: "Specifically, look for possibly artificial or unnatural links pointing to your site that could be intended to manipulate PageRank."
The email went on to point out: "...here are examples of pages that contain inorganic links to your site..."
This was sufficient to panic him into requesting removal of all links, in his words: "...we need to get as many links as possible removed, even if it means we lose some good ones or ones we are not sure about..."
This prompted me to download WMT's Links to Your Site to a spreadsheet and visit the top 125 linking domains. I evaluated each and made notes on the spreadsheet. One fifth of those domains (26) earned the label "suspect". These included scraped content from my site that had been spun, directories using my entry over many subdomains and bloggers that used a high density of contextual linking.
I put this list together in order to still the flapping wings of paranoia. I now have an action plan should I receive a WMT message about backlinks. Until then I'll sit and wait until there's more evidence on backlink penalties.
Another exercise I'm conducting is the "balancing" of keywords usage (as described in a previous post). WMT's Content Keywords is invaluable in assessing whether your onsite keyword usage is top-heavy. I particularly suspect keyword usage in anchor text is a temptingly easy "crime" to commit.
Assuming you have a content-rich site I believe you can regain top-rankings on Google, especially if Bing still loves you. The over-optimisation penalty is harsh, like punishing the whole class when the culprit won't own up, but by honest revision of previously "acceptable" SEO tricks there will be a way back...