Exchange would do quite well, I'd imagine, in that scenario. I ran a copy for years on a server at home to handle all my email, mostly as practice for administering an exchange server. That was several versions ago, and it was a bit of a pain in the ass.
The latest versions are much nicer to admin from what I hear.
But exchanges webmail has always been a bit anemic.
I also ran Mercury, but it never seemed stable for me.
You might want to have a look here
http://en.wikipedia.org/wiki/Comparison_of_mail_serversThere's tons of options out there.
Do they explicitly NOT want to go with a hosted solution (like GMAIL)?