Podrías hechar un vistazo a las RFC's que definen el protocolo de e-mail ...
http://www.faqs.org/rfcs/rfc2076.html
(empieza por ahí ...)
Si dicen que es esa cabecera .. tendrás que añadir:
$mailheaders .= "Date-Delivery: $fecha\n\n";
Lo que no sé es $fecha .. que formato tendrá que ser .. tal vez sea UTC .. ahí no sé .. averigüalo antes.
Un saludo,