Ludzie, tak na prawdę to (imo) nie powinno się korzystać z funkcji mail(). Jedyne słuszne rozwiązanie to PHPMailer i wysyłka za pomocą SMTP
Przyłączam się do namowy Zonic'a.
Machnij z palucha fancy formularz pod SMTP z prawidło działającym uwierzytelnianiem przez ssl.
Trzeba sobie stawiać wyżej poprzeczki, a ta jest wysoko ustawiona patrząc na tony fomularzy* siejących w sieci spam poprzez mail()
* co zawdzięczamy lichej jakości wtyczkom do cms-ów