I regularly test out offerings from SEO companies to see what they are doing. The majority of such ventures end up in refunds. (You just need to word your Paypal dispute wisely!)
Anyway. On the 27th of April I put up an ad stating the web address of one of my affected websites. I said I'd lost my rankings on the 24th, that I didn't know why and that I needed an SEO firm to help me. Here are my favourite responses:
"I found no keywords meta tag. The keyword meta tag is still used by some search engines. Consider to add a keyword meta tag."
"Only 5 of your 11 images have keywords in the alt tags. You need to maximize your alt tags."
"We are Experienced SEO and can help you find the cause why google Penalised. On the Comtempary it looks like the Panda Update was Responsible for your Fall."
"Our experts will take in to consideration Google Logic and target only 4 to 5 keywords each page. Our experts smartly integrate keywords in the content based on Google Rule of keyword, Proximity, Density and Frequency."
"I have investigated your website and found your site is still listed in Google but the cached copy of your website is removed. thats the reason it is not ranking in search result for your desire keywords. I will get cached page showing again."
Those were genuine responses from "expert" companies with ratings of 4-5/5 and hundreds of customers singing their praises.
Out of 32 responses to the ad, only 7 firms correctly identified that my website had a spammy link profile and was therefore most likely hit by Penguin considering the date co-incidence.
Just a warning to some of those panicking out there and running to SEO firms. Even the ones listed on third party marketplaces with high rankings and previously good reviews may have absolutely no idea what they are doing.