Под виндой - Exchange + ISA 2000 - настраевается относительно несложно
Если по-хорошему, то sendmail
Если мыл немного, MDaemon, Kerio Mail Server + почовый домен у провайдера и релаинг на него - гемору меньше всего как с настройкой, так и с администрированием.