Prova a inviare l'email a un indirizzo gmail, se arriva e a hotmail no, allora è dovuto al sistema di difesa di hotmail.
Qui trovi spiegato (in inglese) cosa sono i record mx.
Io non ho idea di come impostare i record mx correttamente perchè queste informazioni le avevo trovate su internet.
Un altro metodo più semplice e rapido per ovviare a questo problema, è quello di collegarsi al server SMTP di gmail, ad esempio, e inviare le email attraverso di esso. Puoi fare questo in modo semplice utilizzando la classe PHPMailer anzichè la semplice funzione mail().
In questa discussione ho scritto dove scaricare PHPMailer e ho messo anche un esempio su come utilizzarla. Se continui nella discussione ho scritto in qualche post successivo (qui) un link a un esempio di come usare PHPMailer collegandosi al server SMTP di gmail.