Choosing A Managed Security Provider?

Gothmolly asks: "There are a growing number of Managed Security Providers (MSP) out there. Basically, these guys drop a firewall in your company, then manage it remotely. Defendnet also offers VPN and (I hear) in-line Anti-Virus solutions. Places like MyCIO and ISS basically do the same thing. How does one evaluate the capabilities of a Managed Security Provider?"