--- a/keyexchange/tests/test_filtering.py
+++ b/keyexchange/tests/test_filtering.py
@@ -184,19 +184,31 @@ class TestIPFiltering(unittest.TestCase)
                 #   - add 10 elements
                 #   - remove 1
                 #   - save the list
                 self.blacklist.update()
 
                 for i in range(10):
                     self.blacklist.add(self.name + str(i))
 
-                # remove a random element
+                # Remove a random element.
+                # It's possible that multiple threads pick the same
+                # element to remove, producing a KeyError.  Loop until
+                # one is successfully removed.
                 ips = list(self.blacklist.ips)
-                self.blacklist.remove(random.choice(ips))
+                for _ in xrange(1000):
+                    try:
+                        self.blacklist.remove(random.choice(ips))
+                        break
+                    except KeyError:
+                        pass
+                else:
+                    msg = "Repeated collisions while trying to remove an "\
+                          "element, something is almost certainly wrong."
+                    raise Exception(msg)
 
                 # save the list
                 self.blacklist.save()
 
         workers = [Worker(str(i), blacklist) for i in range(10)]
         for worker in workers:
             worker.start()