@sixsigmaus & Jez123 - could you provide some details which would be helpful for members?
OK, here's what I did, FWIW.
My main site was hit with Penguin 1.0 on 24/4/12 and I lost approximately 70% of traffic. 100% of quality traffic.
As soon as I knew it was link related I removed any links that I could control, Opera blog and a related sitewide of my own, plus links from a friend who always generously linked to any new pages I put up.
Then I waited for a while and in that time redesigned the site and tried to gain loading speed by moving all images to the cloud to speed everything up. De optimised some of the pages titles and any excessive KW counts.
All of this caused the site to drop further. Most likely due to loss of what quite easily could have been links that google didn't know about or wasn't bothered about.
A while after that I looked closely at my backlink profile and discovered that someone had run xrumer (or similar spam tool) on my site and added loads of spam forum profile links and bookmarks. This turned out to be a misunderstanding by someone that was helping me to put a link bait idea that we had had and he instructed someone in India to add 1,000 links pointing at my site. He apologised and did what he could to help me get those removed.
I also found that an article that I had written in 2004 had been syndicated to 100's of really spammy article sites. I couldn't do anything about those so when the disavow tool was launched I disavowed them along with some other nasties that I still don't know where they came from.
All this time, no gains, most decent KW's were way out/ Page 12 and beyond and in one case page 50 to 55 (it fluctuated).
I pretty much gave up at this point and launched 2 more sites to cover 2 of my main sites main niches. And concentrated on these for as while.
In May this year Penguin was updated and my site looked a lot healthier. The main SERP's came mostly to page 3 to 5 and some longer tail stuff was getting about 30% more traffic. About this time I looked at the link profile again and went through the disavow again and caught any links that I had either missed, weren't present or were new and submitted it.
I didn't do any link building in this time. I was lucky enough to get one of my products written about in the guardian.co.uk (big UK newspaper) and a link from them and then subsequently a few other magazines etc picked up their story and kept my link intact so that was probably quite a powerful trust adding bit of luck. Even with these powerful links, there was no movement on the site's SERPs (this was back in July this year) until Penguin was refreshed this weekend. This tells me that adding links alone will not pull a site out of Penguin. Nothing will happen until the refresh.
The only other thing that I have spent a lot of time doing has been pinning my products on Pinterest. The links that you get from that are nofollow but it's fairly easy to get hundreds or even thousands if your pins are popular (plus you can get some traffic too). I am wondering if these links helped balance my link profile and water down nasties and too much direct anchors. This is just speculation but I believe that it helped.
My site is probably not as strong as before Penguin hit it – and it may even get stronger after another Penguin update (just a feeling due to some KW's seemingly still “penalised”) but I am not complaining. The site is my main business as well as my main income so I am happy to have it returned to me. Lets hope it sticks.
The main thing is that it seems that you WILL NOT recover from Penguin without a Penguin refresh. It is possible to do though.
So to recap. The things I think that helped are:
Removing / disavowing bad links.
Diluting links with nofollow, no anchor links. Such as social media
Getting extremely good new links that are unsolicited preferably without direct anchor text.
Being good and keeping your nose clean for 16 months.