If you need to scale to huge levels (which I doubt, since a couple of Exchange boxes were working) you need sendmail, and you should buy the GUI and a support contract from sendmail.com (because sendmail is difficult to understand and configure otherwise).
If you don't intend to dominate the world with your Email servers, I recommend Postfix instead. It's a lot easier and the basic design is more secure than Sendmail's old-fashioned monolithic privileged daemon approach.
I wouldn't bother with qmail, personally. There are licensing and support issues with qmail (among them, the fact that the author runs a "one-man show" and may get hit by a truck one of these days).
MailScanner can be used to integrate virus scanning, spam checking, and real-time black hole lists with any sendmail-compatible transport. I highly recommend MailScanner, and use it on all my mailservers. At home it uses the free f-prot virus scanner and spamassassin, at work it uses two commercial scanners, spamassassin, and both locally maintained and remote RBLs.
We did not receive a SINGLE sobig.F virus during the recent fooferaw - I did NO special preparation to the systems but they rejected several thousand sobigs without any problems. I see this as a testimony to the robust design of MailScanner.
If you want web integration you should check out IMP and the HORDE at horde.org.
If you want maildirs and/or IMAP folders-in-folders, you should check out
http://www.courier-mta.org.
My users generally use Pegasus or Eudora on the desktop, and the stock Red Hat IMAP daemon.
Remember, an Email solution AT MINIMUM includes a Mail User Agent (such as Pegasus, Eudora, Imp, the Bat!, or even the dreaded virus-festival Outlook) a Mail Transfer Agent (such as sendmail, exim, qmail, or postfix) and a Mail Delivery Agent (such as the UW IMAPd, procmail, Cyrus, Qpopper, etc.) as well as optional additional components such as virus scanners, mime defangers, decompressors, secure transport layers, spam filtering, blackhole lists, and so on.
Get the company to fund you to do a home network system first, as a pilot. They should pay for your DSL line and give you some of their older lamer computers and a hub with a few lengths of Cat 5. You should pay for any extras, like a fast new computer for your own workstation and any fancy wiring to get workstations into bedrooms or kitchens etc.