That is correct.  Most SMTP gateways add the header on submission if it is missing.  At least a few other MUA programs do not automatically add the Date header, they let the SMTP server do it.  I have one person who sends me email that saw this same problem (I had my server set to reject messages without the date header), and they weren't using smtplib to send.  (I think the sender used Exchange, though I don't remember for sure.)