Security concerns are very valid -- security is probably the key reason why most organizations won't use a service provider. So much important corporate information is in email. There's lots of sophisticated ways now that these service providers are able to separate your data from other customers' data and lock that down. There'll be employees within the service provider, and they're the only ones that have access and authorization to your email.
Something else to think about is how they encrypt the data -- how they encrypt your email when it's in transit between you and their data center, as well as how it's encrypted at rest at their place. But those two pieces are available with most of these email archiving services now.
20 Aug 2008