Gnu Privacy Guard/PGP and S/MIME both provide encrypted, end-to-end email. Or you could share the same mail server (infrastructure), or set up a VPN with your own DNS, smtp etc.
GPG and S/MIME does leave headers open -- but some form of traffic analysis would be possible even with "direct" SMTP.
One way of defeating traffic analysis is to combine GnuPG/PGP with mix-master remailers (onion routing for email, similar in principle to TOR). As with TOR, many (exit) nodes are probably operated (directly or indirectly) by intelligence agencies.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumb...
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29....
Somewhat amusingly, one of the authors worked for AT&T. Maybe he knew something about why you'd want an off the record channel for email ? ;-)
The difficulty with both S/MIME and GnuPG is key/trust-management - an unsolved problem. With S/MIME you can set up certificates internally with e.g: Active Directory. With GnuPG you could perhaps set up/recommend all users to trust a "central" keypair, and use that keypair to sign all user keys.
I'd say eg: Thunderbird with a plugin for GnuPG is about as easy as things are going to get -- without some user education (wrt trust) -- you won't actually get any security anyway.