You want to at least have some control over the hardware. Disk encryption on a dedicated server or (even more ideally) a caged, locked, colocated rack.

The system administrators of anything multi-tenant can access your data. The problem is they probably don't care. It's up to you where to draw that line, though.

"Administering a mail host is sort of like being a nurse; there's a brief period at the start when the thought of seeing people's privates might be vaguely titillating in a theoretical sense, but that sort of thing doesn't last long when it's up against the daily reality of mess. Now that I think about it, administering a mail host is exactly like being a nurse, only people die slightly less often."