Prueba con Google Apps,
http://www.google.com/a
solamente desde el panel de control de tus dominios apuntas los mx a google, verificas q eres el duenio del dominio y puedes crear hasta 50 cuentas de correo gratuitas con la interface misma de gmail para tu dominio.
yo lo uso sin problemas en mas de 40 dominios y es fabuloso!! cualquier cosa dime y armo un tutorial....