
Você tem que conversar com o pessoal que hospeda o seu site. O IP onde eles hospedaram o seu site e que executa a função mail deve estar em blacklist. Eles vão ter que escrever para uma série de DNSBL (DNS black lists) tipo Spamcop, Spamhaus etc. Indiretamente significa que eles estão hospedando também pessoas que usam com descuidado da função mail, daí vem o blacklist.