http://sendgrid.com. Lo uso personalmente en mis proyectos por otras razones, pero va muy bien y rápido (usa la infraestructura en la nube de Amazon SES) Y además... es de pago! (no te dan una IP propia, y correo certificado con claves gratis ni en un universo paralelo)
Yo no sé de que protesta el cliente; a ver si cree que cuando mandas algo desde GMail o Hotmail va muchísimo más rápido.
Para que no le lleguen hay muchísimas razones. Por ejemplo,, Yahoo comenzó a rechazar a mi antigua compañía de correo porque enviaba muchos correos a la vez. Resultado? A los usuario ni siquiera les llegaba a la carpeta de Spam. También muchas veces el servicio del lado del que va a recibir no es del todo bueno, y deniega el acceso (el mensaje retorna al que lo ha enviado) o simplemente se toma más tiempo en procesarlo por los filtros anti-spam. Es decir, que enviar un e-mail no es abro una conexión y te lo envío; es que es posible que pase por cientos de máquinas distintas (literalmente, cientos, a veces menos, a veces más)