Spróbuj dodać nagłówki do wiadomości, np. coś na wzór tych w ostatnim przykładzie na dole strony:
https://pl.wikibooks.org/wiki/PHP/Wysy%C5%82anie_e-maili#Przyk.C5.82ady
Niestety funkcja mail() nie jest zbyt wygodna i bywa problematyczna, dlatego polecam użycie biblioteki PHPMailer lub Swift Mailer i wysyłanie przez SMTP.