Redundancy redundancy redundancy.
Thats the most important thing
I am guessing that it is a small company, if so and you are not handling government secrets
you can contact gmail about email with your own domain.
Alternatively Office Live has some nice cheap plans as well and has the added benefit of being, well, office live
Document sharing and all that stuff to go along with it.
Once you get larger you can look at running an email server yourself, for a small company it is not really worth the cost of self hosting IMHO. The risk of losing all your email or having it down is too great. The best method of preventing that is shadowed servers at 2 separate locations. And that is just a little out of my ken.