Should I trust an SEO company that got penalized by Google?

[Jake]

Perhaps they over promoted their own site which lost search ranking as part of a penalty, it's possible but unlikely that some would have tracked the ranking of a competitor's sales site and it's less likely that they would have stats on the competitors clients, could just be smoke.

There certainly is some risk when SEO companies have to meet a quote or promised performance, it may be better to oversee your own SEO campaign, hiring different specialists to create different back-link types. You ma be in a better position to control the rate and source of new backlinks.