PHP provavelmente não é o remetente real do eamil.
Verifique os arquivos de log do servidor de e-mail (sendmail, exim, etc.) (no debian, os logs estão em / var).
Verifique a caixa de e-mail admin @ ou postmaster @ para avisos de falha na entrega.
Verifique se o nosso ISP está publicando o RDNS para o IP do seu servidor com o nome de domínio incorreto.
Embora seja menos provável, verifique o SPF do seu domínio no seu registrador.