Si tenéis el capital podéis inscribirte en IronPort,
http://www.cisco.com/web/about/ac49/.../ironport.html, también usar SenderScore
Senderbase.com es parte de IronPort.
Para hotmail podeis usar el servicio de JMRP y SDNS. Para que el email llegue a la mayoría de proveedores configura SPF, senderid, DKIM, siempre envía email autenticado, configura el reverse dns al host de tu servidor de email, limpia la IP si está reportada como spam, y si la IP ya ha estado reportada como spam entonces lo mejor es usar otra IP.