Странно, что ещё никто не порекомендовал Alt-N MDaemon, который, в общем и целом (насколько мне помнится) с вышеописанными задачами справляется. Ну, и ещё Symantec Messaging Gateway в качестве антиспама, и, по идее, должно наступить счастье, благо настраивается достаточно просто.
Ещё слышал хорошие отзывы про почтовик Zimbra, который тут уже советовали пару раз. Но, если есть хоть малейшая возможность убедить ставить Exchange — убеждайте до последнего.