Whitey - 7:31 am on Apr 23, 2013 (gmt 0)
@asusplay - just some questions first. Did you :
- have good knowledge about the "unnatural" nature of those links during the build period
- think they may become a liability at some stage in the future
- benefit $$'s from increased traffic/income during the period they were in effect
Then I think you need to weigh up who's responsible for the "damage". Is it your SEO entirely or partly yourself, and what the benefit v damage is.
Then work out if you're going to fix it or not, with or without the resource of the fired SEO company who you might consider charging or requiring them to contribute to the rapid clean up work, even though you may forbid them from touching your site again.
Then I'd do all possible to strengthen your link profile, so that your site can survive, fast. Use the disavow tool carefully, rebuild quality links urgently, diversify anchor text, 404 heavily linked to pages and set up new pages in replacement, where sensible.
IMO prepare for a complete cleanout of sites in the major Penguin 2 update, due soon, and treat the "unnatural links notice" as the most notice anyone's ever had to take steps to purify their sites. Google has shown no mercy in Panda/Penguin and my guess is they are only 75% done before axing the final major grouping of site's into the bin.
I'm being dramatic, but as recent history shows, Google takes no prisoners in these major updates. And Google seems clear about the sites it wants out of it's results.
If Google has discounted some of those links, and you can guess which one's they are, disavowing them may reinforce the act of faith that Google might be looking for.