Había visto excusas absurdas, pero esta..
Cita: 2- Que cambie de nombre de dominio (lo que, obviamente, también es inviable)
Cita: ¿Son estas soluciones las habituales? ¿No puede hacer nada la empresa proveedora de hosting para solucionar el problema?
La solución que debe implementar es muy simple, la empresa de hosting debe proporcionar buenas protecciones de SPAM entrante y saliente, de ese modo no tendrá este problema, si la empresa no puede dar ese mínimo servicio, creo que debería pensar en conseguirse un proveedor más responsable.
Es ridículo solicitar que cambie a un server dedicado cuando tiene un alto tráfico de email y casi todo es originado por SPAM, eso lo debe solucionar el soporte de la empresa.
Saludos,