Invece di reinventare la ruota con mail(), usa una classe come PHPMailer

https://github.com/PHPMailer/PHPMailer

Ma sopratutto, usa indirizzi email tuoi per from, reply to etc perchè lo spoofing del mittente fa sicuramente bloccare le mail dai filtri anti spam.