It becomes easy when you make your employees use a VPN to access yor exchange server directly and have a smarthost mail server (sendmail, qmail, whatever that is set up secure) on a dmz that actualy is exposed to the internet at large. To the ISP the VPN traffic does not look like SMTP. You lose complexity and gain encrypted comunications.
Also if you are just using imap/pop other systems (besides echange) can be set up with the imap/pop auth allowing inbound imap/pop connections.