even with load balancing and redundant everything, you are not going to achieve 100% uptime.
We had 100% uptime on our mail server setup with load balancing since December, then our DC performed some maintenance and scheduled an outage, and there goes that
I guess you could cluster across Data Centers and get closer to 100%, but that would be cost prohibitive and still would not ensure 100%.
You should probably aim for 99.99% mail uptime, which is certainly achievable - but, the provider needs to put ALOT of effort into achieving that record over a prolonged period of time. Having said this, it is completely possible to have a very close to 0% mail loss - so, even if the service is down, mail is getting spooled. This is something that is attainable.