Ask HN: Looking for hosted email solutions, outside the USA.

We've been using Google Apps for a couple years now. The plain problem is, google loses our mail. It is inconsistent and difficult to diagnose and as far as google is concerned, the mail never showed up on their end. But we know we're losing mail.

For various reasons, we'd like to host outside the USA. We're pretty flexible as to the country, so long as the infrastructure is decent. I don't want to debate this requirement, I don't necessarily even agree with it, but "the boss" is involved and we want to keep the boss happy, right? (This is also why, even if we fix the issue with Google, we need to migrate. No disparagement meant for google, they provide a great value, just not meeting our needs now.)

So, can anyone recommend an email hosting provider?

Preferably, an organization with a significant reputation, who cares about providing good service, who would be really embarrassed to do wrong by us (e.g.: not some tiny shop) and who either specializes in this service, or is really very good at it.

Any service that specializes in secure communications gets bonus points. I'm looking at hush mail, but they're a US corporation, though it seems their servers are in Canada. our employees use iOS devices and laptops, so I'm not sure hush is a good fit, unless they have an iPhone App.

Thanks in advance for any advice!

PS- I did try to search hacker news for this stuff, but a couple attempts didn't produce much. Google searches produce a lot of questionable recommendations, and stack exchange, et. al. close questions where an opinion is being solicited.

PPS-- I am open to the possibility of hosing it ourselves, though I don't like the idea. I have run my own mail servers in the past for many years and don't recall that period fondly. But, if there's a turnkey linux appliance that would do it, that could work. I looked at TurnkeyLinux.org's Zimbra appliance, but zimbra is a confusing thing, it isn't clear what the differences between the commercial and open source version are, and it seems more interested in providing webmail than POP/SMTP mail. But maybe that's what I need. Any Zimbra experts out there?