I do not think anyone can recommend the "best" company as the criteria for "best" depend on your business needs.
That being said, I would recommend sending a request for proposal (or call for tender, I never know the correct name for this) to 5 companies with local offices so you can meet the ethical hackers if needed. This is good to avoid relying on a bunch of "not so white hackers" with little knowledge of collateral damages and potential impact of the pentest on the information system.
Make sure the intruders do not rely on automated tools. I have seen Eeye/ISS reports labelled as actual pentests reports, sold at pentest prices. A good pentest on a 3/3 application requires at least 8-10 days from my experience. These figures should be adapted to the complexity of the infrastructure of course.
I would also ask for information regarding
- system tests vs application tests. The latter cannot be automated to be effective, but both are necessary for a pentest to be meaningful
- the pentest methodology (do they have anything set or do they do it "as they feel" for each project),
- audit trails gathering (all traffic between the pentest lab and your information system should be archived)
- alert processes (what should they do if a critical vulnerability is discovered) and so on
Many companies with little knowledge of professional penetration testing sell intrusion services, from my point of view it is your job to select the best one, nobody on Slashdot can do that for you.