We'd like to set up our 500 clients on one email server where each one
of them can access it online, like gmail.

The challenge is that each one of our clients has a different domain
name. How would we go about setting up a service like this?

Requirements:
-webmail access
-easy to use interface
-customizable
-very reliable

I have very good expereicne with this one. Its interface looks like Outlook.

http://www.icewarp.com/