Allora, non ho controllato il codice delle intestazioni della mail, ma sicuramente l'errore è lì.

Anche se le intestazioni delle mail sono standard, un codice che va su un server potrebbe non andare su un altro.
Questo perchè probabilmente il tuo codice non segue esattamente lo standard, e quindi può andare su un server mentre su un altro no.

Io sinceramente mi ero stufato di questa cosa, e non avendo voglia di studiarmi l'rfc delle mail, ho cominciato a usare phpmailer, una classe eccezionale per l'invio di mail, che non mi ha mai dato problemi.

http://phpmailer.codeworxtech.com/

Ciao e buon anno!