I recommend you support POP3/IMAP, but setup the clients primarily with
IMAP. They'll like the ability to have their Sent Items and shared folders
from any IMAP client or Webmail. Cyrus is very fast and stable, I prefer it
over Courier for larger installations. While you are at it, will you add in
virus scanning (amavis + scannerdaemon) or spam protection?

Your options for the SMTP engine is qmail, sendmail, exim and postfix. I
have worked with them all, and they're all pretty good. Find something you
can understand and get some support on. The sendmail.cf is sometimes
daunting -- take a look at that configuration file before you commit to
support sendmail for the duration.

This sticking point I see is a client that support the calendering that
Exchange does. How much do they rely on the calendar sharing functions? If
they don't share their calendars, you can use Palm Desktop 4.1 -- it is very
pretty. Or if they actually own their Outlook clients, you can probably hack
something up with a PST. Just remember "PST = Bad".

Do they have any integrated forms that kick into Exchange? These are also a
bear.

Good luck!
Tony Wasson