A un amigo le pasa lo mismo, tiene que ver mucho el servidor desde donde se hace el mail(), de igual forma revisa los headers que esen completos, hasta donde yo se no hay forma exacta o script ya que Gmail y hotmail crea como una lista (en base a bots como la de los buscadores) para bloquear posibles spammers, saludos y espero alguien sepa.
