First you need to define what services you require. They tend to fall into three categories. Testing (determine how deep the tests should penetrate), remediation (removing flaws in your security), and management (turning over your firewall, IDS, and other securty devices to an outside vendor). The first two are like shampoo ... test, remediate, repeat. The third is the hard one.
Many vendors can perform the penetration testing. Many can perform the remediation. Few can perform the management. Within that short list there have been many consolidations and some vendors have folded up their tents, so the list gets even shorter.
If you're going to attempt to outsource the management talk with their technical people. What tools do they use? Does the vendor write their own security signatures as they discover threats or do they rely on system and software vendors to supply them? Does the vendor perform in-band or out-of-band management? How secure is the management channel? Does the vendor use hardware or software IDS? Do they use appliances or software on a server platform?
What is their response time to a threat? At what point during a threat or attack does the vendor's responsibility end and yours begin? (Ultimately it's all yours.) How will they support the security of legacy systems?
How many of their staff are CISSP certified? How do they vette their people? Can you visit their NOC (or SOC)? Can they supply you with references? That last one is tricky since many of their customers don't want others to know how their networks are secured.
Finally you also have to weigh the cost of outsourcing against the cost of employing a full time security staff.
Good Luck!
