Gmail is rejecting messages without Message-ID unconditionally:

:Could not dispatch registration e-mail: 550 5.7.1 [redacted] Messages missing a valid Message-ID header are 5.7.1 not accepted. For more information, go to 5.7.1 https://support.google.com/mail/?p=RfcMessageNonCompliant and review 5.7.1 RFC 5322 specifications. y7-[redacted] - gsmtp

We send Message-ID iff DKIM is enabled. We should send it in every case.