Disclaimer: I don't work for a messaging company of any type but am highly biased by my 15 years of experience managing the network (including email service) for medium sized businesses in the retail and utility sectors.
As of yet I have only moved email infrastructure the opposite way, from outsourced to in-house. Many products claim to reduce complexity, but in fact do not; they only hide the complexity. Many times when I have looked at proposed solutions, there is actually increased complexity based on the number of components in the system and the connection relationships. It now seems to be a growing trend that the "cloud" providers hide or make it very difficult to obtain a useful and detailed systems diagram. What I write about here will hopefully point people on what types of questions to ask when they are evaluating an outsourced messaging service.
In any case where a BC/DR strategy is being addressed, you will need to confront the fact that you just don't know how well a 3rd party or managed service will work no matter what the contract says. With an in-house solution, you can test the architecture in a lab environment and generate a deterministic list of the failure modes. 100% uptime is a misnomer; it does not exist. How will you test the functionality of the service before committing? Is there a record of downtime incidents? Public? What is the communications policy of the service when there is a disruption? What about when security related incidents happen, will you know about it? This should all be in the contract.
With email, you also have to consider where the email filtering is, how it is implemented, and how easily changes can be made to what is blocked. Many 3rd party email continuity solutions force you to change your MX record(s) to point at their gateways. What is their listing policy? Is the policy publicly available? What is the procedure and time-frame for making changes to the blocklist by you? By someone who is blocked? Is it actually possible? How do they measure the effectiveness of the filtering? What about false-positives?
The high-level view of email shows a system of many distributed queues. Create a diagram showing all the queues in a particular configuration and you will see were it will fail. How does the proposed solution stack up (consider the service as a single black box unless you know otherwise)?
Compare the service with a known and well tested in-house solution:
In general, with Exchange, an in-house solution would involve a clustering setup with older versions or the DAG feature in 2010; this will likely mean at least 4 instances of Exchange. You combine that with a load balancer such as produced by F5 (high end) to achieve client continuity. Achieving messaging continuity with the Internet would involve setting up multiple Internet connections and multiple email gateways such as Ironport devices. All this is a serious investment of course, but run the numbers (including in-house talent) in comparison to these "cloud" solutions and you may be surprised at the value achieved with an in-house solution. BTW, there are much cheaper solutions than F5 and Ironport out there that give the same level of continuity. The outsource looks better to the smaller players here, but even so, with DAG and some Linux knowledge, a smaller shop can do pretty well.
At the end of the day, with any off-premise solution, there is the Internet connection to consider. Ask what the in-house messaging continuity scenario looks like if the Internet is not available.
Google the company and see if they've hired an SEO company to clean up their online image. You will be able to tell this is the case if all you see are links to the big industry magazines that just regurgitate press-releases and other worthless content like sponsored studies, whitepapers, and other corporate shills. It is always a plus if you can easily find discussion boards or email list archives with good and bad feedback about a company. Every company has bad, but the bad is better when you know what it is.