Glad your site is back!!! I'm almost as happy as you are, LOL!
Just a note -- canonicals will solve the problem with duplicate content from multiple versions of your domain as Michael Martinez suggests. The drawback with the canonical tag vs 301's is --
1) It won't stop users from seeing those various domain versions so users may still link to multiple domain versions.
2) The canonical, in theory will consolidate link juice as the 301's will, but anytime there is a redirect/canonical, some of the link juice be lost so you would rather the user only sees one version of the domain rather then letting them link to the other versions and discounting the link value when it's redirected.
3) There are 5 or 6 reasons that the crawlers will ignore canonical tags. With a 301, Google never sees it, it's controlled by the server (depending on how the 301 was created - I recommend server side impementation).
4) Unless you can implement the canonical by template, the 301 is much less work.
I was thinking about you when I saw the following 2 posts. It looks as though they don't apply to you now, but food for thought.
1) Lessons Learned by an Over-Optimizer ---> http://www.seomoz.or...optimizer-14730
2) Google: Go As Far Back As Possible To Remove Paid Links---> http://www.seroundta...inks-14968.html
This is from John Mu at Google, the part that I thought may apply to you is -- Getting A Notification Now Doesn't Mean It Is A New Penalty
Google stepped up their notifications, so if you get a notification today, it doesn't mean it is a new penalty. Google is sending notifications out for old penalties. John explained, "while we have just recently started sending out these messages, they may apply to issues that were already known (and affecting your site's standing in our search results) for a while
Well, another search for
an enigma wrapped in a riddle inside a mystery searching for armed guards that are the tip off that I've found one of G's secret data centers where the meaning of the internet is located -- completed!!!
Aaron Wall at SEO Book said it best (I paraphrase) -- "Most of the important things that you will learn in SEO you will discover by working on your own sites. Sometimes because you made an error such as accidentally removing your site from access to the crawlers. Sometimes it will be positive, sometimes not."
No one can really tell you how to fix your site. Just because it worked for them doesn't mean it will work for you. There are many, many variables the average internet marketer isn't even aware of that makes your situation different. You would really have to be a software engineer to appreciate the degree to which each situation is different and do exhaustive testing to reach a conclusion. Take their info with a grain of salt. Use their ideas as a basis for focusing your troubleshooting efforts, but don't ever rely on their advice carte-blanche. Or mine -- check it out for yourself. I'll always give you cites to supporting info. If I don't, just ask and I'll be happy to pass it on.
BTW - a generalized view of what the average link graph should look like -- 50% exact match anchor, 40% related and keyword variations (to include synonyms, modifiers, keyword stemming, mis-spellings and permutations), 10% branded or unusual terms such as -- "click here".