diff --git a/Lib/email/test/test_email.py b/Lib/email/test/test_email.py
index c11e84b..513b3e5 100644
--- a/Lib/email/test/test_email.py
+++ b/Lib/email/test/test_email.py
@@ -12,6 +12,10 @@
 import textwrap
 from cStringIO import StringIO
 from random import choice
+try:
+    from threading import Thread
+except ImportError:
+    from dummy_threading import Thread
 
 import email
 
@@ -33,7 +37,7 @@
 from email import base64MIME
 from email import quopriMIME
 
-from test.test_support import findfile, run_unittest
+from test.test_support import findfile, run_unittest, start_threads
 from email.test import __file__ as landmark
 
 
@@ -2412,6 +2416,25 @@
         addrs = Utils.getaddresses(['User ((nested comment)) <foo@bar.com>'])
         eq(addrs[0][1], 'foo@bar.com')
 
+    def test_make_msgid_collisions(self):
+        # Test make_msgid uniqueness, even with multiple threads
+        class MsgidsThread(Thread):
+            def run(self):
+                # generate msgids for 3 seconds
+                self.msgids = []
+                append = self.msgids.append
+                make_msgid = Utils.make_msgid
+                clock = time.clock
+                tfin = clock() + 3.0
+                while clock() < tfin:
+                    append(make_msgid())
+
+        threads = [MsgidsThread() for i in range(5)]
+        with start_threads(threads):
+            pass
+        all_ids = sum([t.msgids for t in threads], [])
+        self.assertEqual(len(set(all_ids)), len(all_ids))
+
     def test_utils_quote_unquote(self):
         eq = self.assertEqual
         msg = Message()
diff --git a/Lib/email/utils.py b/Lib/email/utils.py
index c976021..ac13f49 100644
--- a/Lib/email/utils.py
+++ b/Lib/email/utils.py
@@ -177,21 +177,20 @@
 def make_msgid(idstring=None):
     """Returns a string suitable for RFC 2822 compliant Message-ID, e.g:
 
-    <20020201195627.33539.96671@nightshade.la.mastaler.com>
+    <142480216486.20800.16526388040877946887@nightshade.la.mastaler.com>
 
     Optional idstring if given is a string used to strengthen the
     uniqueness of the message id.
     """
-    timeval = time.time()
-    utcdate = time.strftime('%Y%m%d%H%M%S', time.gmtime(timeval))
+    timeval = int(time.time()*100)
     pid = os.getpid()
-    randint = random.randrange(100000)
+    randint = random.getrandbits(64)
     if idstring is None:
         idstring = ''
     else:
         idstring = '.' + idstring
     idhost = socket.getfqdn()
-    msgid = '<%s.%s.%s%s@%s>' % (utcdate, pid, randint, idstring, idhost)
+    msgid = '<%d.%d.%d%s@%s>' % (timeval, pid, randint, idstring, idhost)
     return msgid
 
 
diff --git a/Misc/NEWS b/Misc/NEWS
index a666032..4567a44 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -15,6 +15,9 @@
 Library
 -------
 
+- Issue #6598: Increased time precision and random number range in
+  email.utils.make_msgid() to strengthen the uniqueness of the message ID.
+
 - Issue #24091: Fixed various crashes in corner cases in cElementTree.
 
 - Issue #15267: HTTPConnection.request() now is compatibile with old-style