That's just paranoia. Everyone with administrative/root access to the mail server could read them, not that they care what's in there usually. The fact that someone is paying for their mailbox or not has nothing to do with that. You are probably safer with the big names, at least they have established protocols and guidelines for privacy...
Besides you can have your @yourdomain.com email with google too, for free. Ever heard of google apps? http://www.google.com/a/help/intl/en/index.html