The more I think about Penguin, the more crazy the idea of links removal seems to me.
One of my sites was hit badly on April 24th. We lost some 60-70% of organic Google traffic. First, I simply ignored the problem, was busy doing other things. Only 2 weeks ago I started to analyze things. Did proper damage control report to figure out which pages and keywords lost traffic and how much. Tried to run some ranking reports - these are difficult, you never know which results are affected by your search history / session. Even if you are using the incognito mode in IE, FF or Chrome you often run several queries at a time and this already makes history. See Adwords Search Query Terms report and you will see that some ads were displayed and clicked on weird keywords and Match Type is: Session-based. I believe they serve organics on that basis, too. Anyway, they are somewhat reliable.
The result of the audit is as follows. Promoted Category pages - these were actively promoted with all types of links but most of their links come from link swaps done in 2004-2006. After penguin they dropped for some keywords but did not for other money keywords. Not-promoted Category pages - these were not promoted heavily and always ranked basing on internal links. They still rank fine in most cases. Product page - we never made any promotion for prudct pages. All of them have unique content (descriptions) and added value in a form of various tools that competitors lack. They used to rank on page1 just on internal links but now went to page 10 or further.
We tend to think about Penguin as a penalty algo that will de-rank pages with overdone links.
So I made an experiment and put some links with targetted anchor text to affected Category pages. What happened: 1/ Page ranks for [keyword] on page1 2/ Penguin comes - page drops to page10 or further for this [keyword] 3/ I add a few (less than 5) links from sites with some links and PR. Links have [keyword] as anchor text. 4/ Page shows back up on page3 for the [keyword]
So I set up another experiment with a set of different pages that dropped to see if this can work and I already see some movement.
What bothers me more is the loss of traffic for the product pages. These pages were not promoted in the past so they used to rank due to internal linking (we actually under-do it on that site) and domain authority. The drop may mean that the domain authority dropped. Which would mean that Penguin simply devalued some links and the site started to be ranked without them (martinibuster was already suggesting it several times).
All the above lead me to following conclucions: 1. conclusion that Penguin does not prevent a page to rank again for a keyword. 2. loss of pages ranking from internal links seems to stem from domain authority loss which would mean devaluation of inbound links. 3. perhaps cleaning links for penguinized sites is not that important and we should just move forward?
In regard to your experiments with the newly-created backlinks, the final effects might not show up until the next Penguin data refresh update. So the ranking improvements in your experiments might get wiped out when the new backlinks are factored into Penguin.
Sure, this is what I think about it: it is run offline every once and then and levels the field where regular algo is not able to do it. Still there is no need to remove the links to rank again - all that is bull#*$! developed by Google's PR officer like Matt Cutts.