Presumo sia un classico hosting condiviso.
Devi provare ad usare la libreria PHPMailer per risolvere moltissimi problemi legati agli header e compagnia bella.
Ci sono molti tutorial, cerca su Google.