diff --git a/hgext/notify.py b/hgext/notify.py
--- a/hgext/notify.py
+++ b/hgext/notify.py
@@ -82,6 +82,12 @@
 
 notify.domain
   Default email domain for sender or recipients with no explicit domain.
+  It is also used for the domain part of the ``Message-Id`` when using
+  ``notify.messageidseed``.
+
+notify.messageidseed
+  Create deterministic ``Message-Id`` headers for the mails based on the seed
+  and the revision identifier of the first commit in the changeset.
 
 notify.style
   Style file to use when formatting emails.
@@ -144,6 +150,7 @@
 import email.errors as emailerrors
 import email.parser as emailparser
 import fnmatch
+import hashlib
 import socket
 import time
 
@@ -183,6 +190,9 @@
 configitem('notify', 'domain',
     default=None,
 )
+configitem('notify', 'messageidseed',
+    default=None,
+)
 configitem('notify', 'fromauthor',
     default=None,
 )
@@ -268,6 +278,7 @@
         self.subs = self.subscribers()
         self.merge = self.ui.configbool('notify', 'merge')
         self.showfunc = self.ui.configbool('notify', 'showfunc')
+        self.messageidseed = self.ui.config('notify', 'messageidseed')
         if self.showfunc is None:
             self.showfunc = self.ui.configbool('diff', 'showfunc')
 
@@ -412,10 +423,7 @@
 
         msg[r'X-Hg-Notification'] = r'changeset %s' % ctx
         if not msg[r'Message-Id']:
-            msg[r'Message-Id'] = encoding.strfromlocal(
-                '<hg.%s.%d.%d@%s>' % (ctx, int(time.time()),
-                                      hash(self.repo.root),
-                                      encoding.strtolocal(socket.getfqdn())))
+            msg[r'Message-Id'] = messageid(ctx, self.domain, self.messageidseed)
         msg[r'To'] = encoding.strfromlocal(', '.join(sorted(subs)))
 
         msgtext = encoding.strtolocal(msg.as_string())
@@ -517,3 +525,16 @@
 
     if count:
         n.send(ctx, count, data)
+
+def messageid(ctx, domain, messageidseed):
+    if domain and messageidseed:
+        host = domain
+    else:
+        host = encoding.strtolocal(socket.getfqdn())
+    if messageidseed:
+        messagehash = hashlib.sha512(ctx.hex() + messageidseed)
+        messageid = '<hg.%s@%s>' % (messagehash.hexdigest()[:64], host)
+    else:
+        messageid = '<hg.%s.%d.%d@%s>' % (ctx, int(time.time()),
+                                          hash(ctx.repo().root), host)
+    return encoding.strfromlocal(messageid)
diff --git a/tests/test-notify.t b/tests/test-notify.t
--- a/tests/test-notify.t
+++ b/tests/test-notify.t
@@ -99,7 +99,13 @@
     "/long/path/repository" into "repository". Default: 0.
   
   notify.domain
-    Default email domain for sender or recipients with no explicit domain.
+    Default email domain for sender or recipients with no explicit domain. It is
+    also used for the domain part of the "Message-Id" when using
+    "notify.messageidseed".
+  
+  notify.messageidseed
+    Create deterministic "Message-Id" headers for the mails based on the seed
+    and the revision identifier of the first commit in the changeset.
   
   notify.style
     Style file to use when formatting emails.
@@ -190,7 +196,7 @@
 of the very long subject line
 pull (minimal config)
 
-  $ hg --traceback --cwd b pull ../a | "$PYTHON" $TESTTMP/filter.py
+  $ hg --traceback --cwd b --config notify.domain=example.com --config notify.messageidseed=example pull ../a | "$PYTHON" $TESTTMP/filter.py
   pulling from ../a
   searching for changes
   adding changesets
@@ -203,10 +209,10 @@
   Content-Transfer-Encoding: 7bit
   Date: * (glob)
   Subject: changeset in $TESTTMP/b: b
-  From: test
+  From: test@example.com
   X-Hg-Notification: changeset 00a13f371396
-  Message-Id: <*> (glob)
-  To: baz, foo@bar
+  Message-Id: <hg.ba3098a36bd4c297288d16788623a841f81f618ea961a0f0fd65de7eb1191b66@example.com>
+  To: baz@example.com, foo@bar
   
   changeset 00a13f371396 in $TESTTMP/b
   details: $TESTTMP/b?cmd=changeset;node=00a13f371396