Pues compañías que bien pueden cumplir con lo que requieres podrían ser:
www.theplanet.com (recomendado)
www.rackspace.com www.liquidweb.com (recomendado)
www.layeredtech.com
En cualquiera de las tres no tendras problema, y quisa sean mucho mejor que brinkster. Checalo en webhostingtalk¡
En cuanto a lo del sistema webmail te dejo unos cuantos links para que los veas.
http://atmail.com/index.php http://www.socketmail.com/site/home/
Saludos¡