Předpokládal bych, že může být chyba někde na SMTP serveru poskytovatele, ten by mohl poradit, protože je určitě schopen sledovat daný traffic. Další možností je, že to chytá spam filtr. Zde - http://www.cesky-hosting.cz/pro-zakazniky/napoveda /php-skripty.html jsou některá doporučení jak používat funkci mail (třeba hlavičky).