diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -3464,6 +3464,7 @@
     'PhabricatorMacroTransactionType' => 'applications/macro/xaction/PhabricatorMacroTransactionType.php',
     'PhabricatorMacroViewController' => 'applications/macro/controller/PhabricatorMacroViewController.php',
     'PhabricatorMailAdapter' => 'applications/metamta/adapter/PhabricatorMailAdapter.php',
+    'PhabricatorMailAdapterTestCase' => 'applications/metamta/adapter/__tests__/PhabricatorMailAdapterTestCase.php',
     'PhabricatorMailAmazonSESAdapter' => 'applications/metamta/adapter/PhabricatorMailAmazonSESAdapter.php',
     'PhabricatorMailAmazonSNSAdapter' => 'applications/metamta/adapter/PhabricatorMailAmazonSNSAdapter.php',
     'PhabricatorMailAttachment' => 'applications/metamta/message/PhabricatorMailAttachment.php',
@@ -9425,6 +9426,7 @@
     'PhabricatorMacroTransactionType' => 'PhabricatorModularTransactionType',
     'PhabricatorMacroViewController' => 'PhabricatorMacroController',
     'PhabricatorMailAdapter' => 'Phobject',
+    'PhabricatorMailAdapterTestCase' => 'PhabricatorTestCase',
     'PhabricatorMailAmazonSESAdapter' => 'PhabricatorMailAdapter',
     'PhabricatorMailAmazonSNSAdapter' => 'PhabricatorMailAdapter',
     'PhabricatorMailAttachment' => 'Phobject',
diff --git a/src/applications/metamta/adapter/PhabricatorMailAdapter.php b/src/applications/metamta/adapter/PhabricatorMailAdapter.php
--- a/src/applications/metamta/adapter/PhabricatorMailAdapter.php
+++ b/src/applications/metamta/adapter/PhabricatorMailAdapter.php
@@ -137,4 +137,37 @@
 
   abstract public function newDefaultOptions();
 
+  final protected function guessIfHostSupportsMessageID($config, $host) {
+    // See T13265. Mailers like "SMTP" and "sendmail" usually allow us to
+    // set the "Message-ID" header to a value we choose, but we may not be
+    // able to if the mailer is being used as API glue and the outbound
+    // pathway ends up routing to a service with an SMTP API that selects
+    // its own "Message-ID" header, like Amazon SES.
+
+    // If users configured a behavior explicitly, use that behavior.
+    if ($config !== null) {
+      return $config;
+    }
+
+    // If the server we're connecting to is part of a service that we know
+    // does not support "Message-ID", guess that we don't support "Message-ID".
+    if ($host !== null) {
+      $host_blocklist = array(
+        '/\.amazonaws\.com\z/',
+        '/\.postmarkapp\.com\z/',
+        '/\.sendgrid\.net\z/',
+      );
+
+      $host = phutil_utf8_strtolower($host);
+      foreach ($host_blocklist as $regexp) {
+        if (preg_match($regexp, $host)) {
+          return false;
+        }
+      }
+    }
+
+    return true;
+  }
+
+
 }
diff --git a/src/applications/metamta/adapter/PhabricatorMailAmazonSESAdapter.php b/src/applications/metamta/adapter/PhabricatorMailAmazonSESAdapter.php
--- a/src/applications/metamta/adapter/PhabricatorMailAmazonSESAdapter.php
+++ b/src/applications/metamta/adapter/PhabricatorMailAmazonSESAdapter.php
@@ -11,10 +11,6 @@
     );
   }
 
-  public function supportsMessageIDHeader() {
-    return false;
-  }
-
   protected function validateOptions(array $options) {
     PhutilTypeSpec::checkMap(
       $options,
diff --git a/src/applications/metamta/adapter/PhabricatorMailPostmarkAdapter.php b/src/applications/metamta/adapter/PhabricatorMailPostmarkAdapter.php
--- a/src/applications/metamta/adapter/PhabricatorMailPostmarkAdapter.php
+++ b/src/applications/metamta/adapter/PhabricatorMailPostmarkAdapter.php
@@ -11,10 +11,6 @@
     );
   }
 
-  public function supportsMessageIDHeader() {
-    return true;
-  }
-
   protected function validateOptions(array $options) {
     PhutilTypeSpec::checkMap(
       $options,
diff --git a/src/applications/metamta/adapter/PhabricatorMailSMTPAdapter.php b/src/applications/metamta/adapter/PhabricatorMailSMTPAdapter.php
--- a/src/applications/metamta/adapter/PhabricatorMailSMTPAdapter.php
+++ b/src/applications/metamta/adapter/PhabricatorMailSMTPAdapter.php
@@ -12,7 +12,9 @@
   }
 
   public function supportsMessageIDHeader() {
-    return true;
+    return $this->guessIfHostSupportsMessageID(
+      $this->getOption('message-id'),
+      $this->getOption('host'));
   }
 
   protected function validateOptions(array $options) {
@@ -24,6 +26,7 @@
         'user' => 'string|null',
         'password' => 'string|null',
         'protocol' => 'string|null',
+        'message-id' => 'bool|null',
       ));
   }
 
@@ -34,6 +37,7 @@
       'user' => null,
       'password' => null,
       'protocol' => null,
+      'message-id' => null,
     );
   }
 
diff --git a/src/applications/metamta/adapter/PhabricatorMailSendmailAdapter.php b/src/applications/metamta/adapter/PhabricatorMailSendmailAdapter.php
--- a/src/applications/metamta/adapter/PhabricatorMailSendmailAdapter.php
+++ b/src/applications/metamta/adapter/PhabricatorMailSendmailAdapter.php
@@ -5,7 +5,6 @@
 
   const ADAPTERTYPE = 'sendmail';
 
-
   public function getSupportedMessageTypes() {
     return array(
       PhabricatorMailEmailMessage::MESSAGETYPE,
@@ -13,20 +12,22 @@
   }
 
   public function supportsMessageIDHeader() {
-    return true;
+    return $this->guessIfHostSupportsMessageID(
+      $this->getOption('message-id'),
+      null);
   }
 
   protected function validateOptions(array $options) {
     PhutilTypeSpec::checkMap(
       $options,
       array(
-        'encoding' => 'string',
+        'message-id' => 'bool|null',
       ));
   }
 
   public function newDefaultOptions() {
     return array(
-      'encoding' => 'base64',
+      'message-id' => null,
     );
   }
 
diff --git a/src/applications/metamta/adapter/__tests__/PhabricatorMailAdapterTestCase.php b/src/applications/metamta/adapter/__tests__/PhabricatorMailAdapterTestCase.php
new file mode 100644
--- /dev/null
+++ b/src/applications/metamta/adapter/__tests__/PhabricatorMailAdapterTestCase.php
@@ -0,0 +1,96 @@
+<?php
+
+final class PhabricatorMailAdapterTestCase
+  extends PhabricatorTestCase {
+
+  public function testSupportsMessageID() {
+    $cases = array(
+      array(
+        pht('Amazon SES'),
+        false,
+        new PhabricatorMailAmazonSESAdapter(),
+        array(
+          'access-key' => 'test',
+          'secret-key' => 'test',
+          'endpoint' => 'test',
+        ),
+      ),
+
+      array(
+        pht('Mailgun'),
+        true,
+        new PhabricatorMailMailgunAdapter(),
+        array(
+          'api-key' => 'test',
+          'domain' => 'test',
+          'api-hostname' => 'test',
+        ),
+      ),
+
+      array(
+        pht('Sendmail'),
+        true,
+        new PhabricatorMailSendmailAdapter(),
+        array(),
+      ),
+
+      array(
+        pht('Sendmail (Explicit Config)'),
+        false,
+        new PhabricatorMailSendmailAdapter(),
+        array(
+          'message-id' => false,
+        ),
+      ),
+
+      array(
+        pht('SMTP (Local)'),
+        true,
+        new PhabricatorMailSMTPAdapter(),
+        array(),
+      ),
+
+      array(
+        pht('SMTP (Local + Explicit)'),
+        false,
+        new PhabricatorMailSMTPAdapter(),
+        array(
+          'message-id' => false,
+        ),
+      ),
+
+      array(
+        pht('SMTP (AWS)'),
+        false,
+        new PhabricatorMailSMTPAdapter(),
+        array(
+          'host' => 'test.amazonaws.com',
+        ),
+      ),
+
+      array(
+        pht('SMTP (AWS + Explicit)'),
+        true,
+        new PhabricatorMailSMTPAdapter(),
+        array(
+          'host' => 'test.amazonaws.com',
+          'message-id' => true,
+        ),
+      ),
+
+    );
+
+    foreach ($cases as $case) {
+      list($label, $expect, $mailer, $options) = $case;
+
+      $defaults = $mailer->newDefaultOptions();
+      $mailer->setOptions($options + $defaults);
+
+      $actual = $mailer->supportsMessageIDHeader();
+
+      $this->assertEqual($expect, $actual, pht('Message-ID: %s', $label));
+    }
+  }
+
+
+}
diff --git a/src/docs/user/configuration/configuring_outbound_email.diviner b/src/docs/user/configuration/configuring_outbound_email.diviner
--- a/src/docs/user/configuration/configuring_outbound_email.diviner
+++ b/src/docs/user/configuration/configuring_outbound_email.diviner
@@ -339,9 +339,11 @@
 how to configure it, this option is straightforward. If you have no idea how to
 do any of this, strongly consider using Postmark or Mailgun instead.
 
-To use this mailer, set `type` to `sendmail`. There are no `options` to
-configure.
+To use this mailer, set `type` to `sendmail`, then configure these `options`:
 
+  - `message-id`: Optional bool. Set to `false` if Phabricator will not be
+    able to select a custom "Message-ID" header when sending mail via this
+    mailer. See "Message-ID Headers" below.
 
 Mailer: SMTP
 ============
@@ -361,6 +363,9 @@
   - `password`: Optional string. Password for authentication.
   - `protocol`: Optional string. Set to `tls` or `ssl` if necessary. Use
     `ssl` for Gmail.
+  - `message-id`: Optional bool. Set to `false` if Phabricator will not be
+    able to select a custom "Message-ID" header when sending mail via this
+    mailer. See "Message-ID Headers" below.
 
 
 Disable Mail
@@ -446,6 +451,54 @@
 only one such server, so it will try to send via Mailgun.
 
 
+Message-ID Headers
+==================
+
+Email has a "Message-ID" header which is important for threading messages
+correctly in mail clients. Normally, Phabricator is free to select its own
+"Message-ID" header values for mail it sends.
+
+However, some mailers (including Amazon SES) do not allow selection of custom
+"Message-ID" values and will ignore or replace the "Message-ID" in mail that
+is submitted through them.
+
+When Phabricator adds other mail headers which affect threading, like
+"In-Reply-To", it needs to know if its "Message-ID" headers will be respected
+or not to select header values which will produce good threading behavior. If
+we guess wrong and think we can set a "Message-ID" header when we can't, you
+may get poor threading behavior in mail clients.
+
+For most mailers (like Postmark, Mailgun, and Amazon SES), the correct setting
+will be selected for you automatically, because the behavior of the mailer
+is knowable ahead of time. For example, we know Amazon SES will never respect
+our "Message-ID" headers.
+
+However, if you're sending mail indirectly through a mailer like SMTP or
+Sendmail, the mail might or might not be routing through some mail service
+which will ignore or replace the "Message-ID" header.
+
+For example, your local mailer might submit mail to Mailgun (so "Message-ID"
+will work), or to Amazon SES (so "Message-ID" will not work), or to some other
+mail service (which we may not know anything about). We can't make a reliable
+guess about whether "Message-ID" will be respected or not based only on
+the local mailer configuration.
+
+By default, we check if the mailer has a hostname we recognize as belonging
+to a service which does not allow us to set a "Message-ID" header. If we don't
+recognize the hostname (which is very common, since these services are most
+often configured against the localhost or some other local machine), we assume
+we can set a "Message-ID" header.
+
+If the outbound pathway does not actually allow selection of a "Message-ID"
+header, you can set the `message-id` option on the mailer to `false` to tell
+Phabricator that it should not assume it can select a value for this header.
+
+For example, if you are sending mail via a local Postfix server which then
+forwards the mail to Amazon SES (a service which does not allow selection of
+a "Message-ID" header), your `smtp` configuration in Phabricator should
+specify `"message-id": false`.
+
+
 Next Steps
 ==========