Yeah, from experience, the security companies that I know of, hired by large coperates that I have worked for didn't know their arse from their elbow... it's shocking
If they say they can make you 100% secure, don't trust them
Often the really good penetration testers are ones that have been unemployed for a while and hacked around (self trained), and then trained in house too
I've no recommendations (I do have a few, but they are full time employed), but if they only run a few tools (paros / wireshark / burp /nmap... ) and then hand over your results with a few days, you've not been given a thorough test. (don't get me wrong, I love those tools for quick results, but they only skim the surface)
Before hiring, I would ask for a list of projects they've worked on and confirm this with their previous employer... but even then, I think security companies are often a shame (they seem to be backward thinking in security and forward thinking in certificates and ticking boxes), I've seen self trained individuals get the job done much more thoroughly
My 2 Pence: Don't hire security companies, hire security testers with a track record (or train them in house if you have potential companies).