You said the magic letters - SLA. This is why some companies pay big bucks for outsourced email. They guarantee a % uptime and if the provider doesn't meet it, I believe that you have legal grounds to sue for damages and disruption to business.
Honestly, if email is _that_ critical to you, you're going to have to pay for it.