Hmm, it's a tough one, but it seems like they are saying you have no further problems else, they would certainly state that the site was still in violation.
The standard type of message you see if they still detect problems is more like this:
"Dear site owner or webmaster of http://www.site.com/,We received a request from a site owner to reconsider http://www.site.com/ for compliance with Google's Webmaster Guidelines.**We've reviewed your site and we still see links to your site that violate our quality guidelines.**Specifically, look for possibly artificial or unnatural links pointing to your site that could be intended to manipulate PageRank. Examples of unnatural linking could include buying links to pass PageRank or participating in link schemes.We encourage you to make changes to comply with our quality guidelines. Once you've made these changes, please submit your site for reconsideration in Google's search results.If you find unnatural links to your site that you are unable to control or remove, please provide the details in your reconsideration request.If you have additional questions about how to resolve this issue, please see our Webmaster Help Forum for support."
Now, your message does not have that, but it is still very strangely worded so I would imagine you still have some kind of problems.
What I am seeing with a few clients I have picked up is a cluster of problems. So, they may have a manual penalty, then some penguin issues and some panda issues on top of that.
Additionally, whilst your manual penalty may have been lifted, you could still have a period where you will remain penalised in my experience but that penalty should, at some point, timeout.
But... depending on when you picked up this manual penalty, who knows what other penalties you have picked up in the meanwhile (panda / penguin etc).
Ultimately, it's impossible to give a generic answer here. You need to review the site attempt to identify any remaining algorithmic penalties which there are some fairly good guides available to do that now.
Here are some links that may help:
General content improvement
http://www.seomoz.org/blog/fat-pandas-and-thin-content
**Anchor text ratios **
http://www.bowlerhat.co.uk/blog/seo/anchor-text-ratios-and-link-building/
Penguin
http://www.distilled.net/blog/seo/penguin-strategies/ - complicated
http://www.bowlerhat.co.uk/blog/penguin-diagnosis-and-recovery-strategy/ - a little simpler
Panda
http://www.distilled.net/blog/seo/beating-the-panda-diagnosing-and-rescuing-a-clients-traffic/
http://www.bowlerhat.co.uk/blog/google-panda-problems-and-solutions/
I have had a quick dig in the link profile and it seems you have cleaned up a lot of what is reported in Open Site Explorer so maybe it is just a case of waiting things out a little longer and seeing if a Penguin refresh sorts things out a bit. It's hard to get a real guage of your link profile, anchor text, relevance of linking sites etc based on the current data returned by open site explorer but some general rules that are coming out of the research done by several sites (the microsites and anchor text articles above make for a good read)
- Have at least 50% of your links from topically relevant sites
- keep keyword anchors below 30%
- branded URL anchors should make up about 70% of your link profile
- Ensure that at least two of the top five anchors are branded (really, post penalty, aim for three +)
When you have got to those kind of conservative levels with your link profile then you can be a little more happy that you are going to be able to bounce back but again, it may take time.
It is a frustrating situation and any 'attempt' at sorting this out should be given 110% else you are really going to struggle. I am not really sure what another agency could do to help you at this point other than more of what you are doing and maybe a solid on site review but you are probably in the position where you just have to wait and see (however frustrating that may be).
Let me know how you get on!
Marcus