Spora część hostingów ma zablokowaną funkcję mail, a duża część z tych, które nie mają, jest na czarnych listach z powodu spamu, więc maile i tak nie dojdą.
Dlatego najczęściej się wykorzystuje rozwiązania typu Symfont Mailer lub PHPMailer, które pozwalają wysłać maila przy pomocy zewnętrznego serwera (np. po podaniu danych do swojego konta GMail). Możesz też uderzyć do obsługi swojego hostingu i dopytać się, czy mail() jest zablokowane i jak wysyłać maile.
Są też usługi pokroju FormSpree, które biorą na siebie pełną obsługę formularzy kontaktowych.