Emails from MusicBrainz (edit notes, subscription emails and "contact user" mails to not seem to have a Message-ID header. GMail adds one when it receives an Email: Message-Id: <4e431fdb.e97a440a.5f7c.3472SMTPIN_ADDED@mx.google.com> as did web.de when I was still receiving messages on my adress there: Message-Id: <E1OqHzO-0005P0-00@mx37.web.de>. According to RFC 5322: Though listed as optional in the table in section 3.6, every message SHOULD have a "Message-ID:" field.