eu sei porque está ocorrendo isso. faz o seguinte :

1) Abrir o site http://whatismyipaddress.com/blacklist-check

2) Coloque seu ip e clique em blacklist check

3) Se aparecer algum nome em vermelho verifique quantos mostra

4) Abra seu terminal em ssh e roda o comando "iptables -F"

Se tiver mais de 3 nomes em vermelho significa que o ip da tua vps ou dedicado está em blacklist portanto nao adianta configurar vps ou reverso o problema vai continuar sempre. A solução seria mudar o ip da tua vps pois se estiver listado na blacklist ninguem receberá mais emails mesmo a unica solução é trocar o ip do dedicado e da vps que certamente vai resolver teu problema.Caso após trocar o ip o problema continuar voce vai ter que formatar tua vps e recriar tudo do zero já com ip novo. Lembramos que o comando "iptables -F" retira todas as regras de firewall da tua vps portanto faça esse comando com cautela pois se tiver configurado alguma regra de bloqueio ela vai cair e liberar tudo referente a bloqueio de ips indesejados.Se voce nao tem regras de bloqueio configurada pode rodar o comando normalmente que nao terá problemas, só aviso isso antes pois se rodar o comando e tiver regras de bloqueio de ip configuradas as mesmas terao que serem refeitas. Para listar as regras de firewall atuais pode usar o comando "iptables -L" esse comando vai exibir as regras de firewall ativas ate o momento e caso de nao aparecer nada é porque as regras nao existem. Se nao estiver na blacklist posta que tentaremos resolver.

Sempre falo quando vejo alguem recomendando usar o iptables -F . Façam antes, service iptables stop -> iptables -F -> service iptables save -> service iptables start.