Cámbiate de hosting, si te dan esa respuesta quiere decir que no tienen intenciones de hacer bien su trabajo.
por otro lado si tienes un VPS TU deberias controlar todo el server no?
yo tenia esos problemas hasta que abri todas las ip's del firewall he instale
fail2ban en mi server.
te recomiendo eso para no tener problemas con las ips.
Nota.
RANGOS DE SERVIDORES DE CORREO DE GOOGLE.
sino te sirve puedes usar robtex.com para ver toda la info de un dominio