Bei welchem Hoster liegt die Website denn? Bei Hosteurope z.B. muss man den Mailversand extra freigeben (bzw. eine entsprechende Mailadresse für das Senden konfigurieren) oder der Mailfunktion einen zusätzlichen Parameter (eine im Hostingpaket bestehende Mailadresse) mitgeben.
Viele Grüße Basti