There are several[1] guides[2] that demonstrate how to set up a full-featured and secure e-mail system. Personally, I run my own e-mail on Exchange Server 2010--complete with a multi-copy database availability group and multiple front-end servers--but I'm known for overkill.
Because I like it, I'm good at it, and it plays nice with all my devices that support ActiveSync. Cloud providers have added support for ActiveSync, but I'm too much of a control freak to give up my self-hosted setup (both due to perceived privacy problems and spam concerns). At this point my Exchange environment is a collection of virtual machines spread across two physical machines (and two disk sets in one machine), so my hardware cost is minimal.
My employer uses Exchange (for some reason still running Exchange 2003!!!) and I have always struggled getting mail clients to play properly with exchange. I have finally given up and am running Outlook virtually.
1 - http://flurdy.com/docs/postfix/index.html
2 - http://www.mail-toaster.org/