Currently, Phabricator generates a "Message-ID" only in a subset of cases (roughly: when the message is first-in-thread and we expect the thread may have more than one message).
In cases where it does not generate a message ID, it expects the SMTP server to generate one for it. Servers will generally do this, and some ONLY do this (that is, they ignore IDs from Phabricator and replace them). Thus, several pieces of configuration control whether Phabricator attempts to generate a "Message-ID" at all.
The PHPMailer code has fallback behavior which generates a "<random>@localhost.localdomain" message ID. This is never desirable and ignores Phabricator-level configuration that Message IDs should not be generated.
For now, remove this code: it is never the desired behavior and sometimes explicitly contradicts the intent of configuration.
Possibly, a better change may be to make Phabricator always generate a message ID in cases where it isn't forbidden from doing so by configuration. However, that's a more complicated change and it's not clear if/when it would produce better behavior, so start here for now.