I'm wondering if the expiringdict(1) needs to have locked wrappers for the inherited methods:

    def __delitem__(self, key):
        with self.lock:
            OrderedDict.__delitem__(self, key)

Otherwise, there is a risk that one thread is deleting a key with no lock held, while another thread is running expiringdict.popitem() which holds a lock while calling both __getitem__ and del.  If the first thread runs between the two steps in the second, the race condition would cause a KeyError.

This might explain why you've observed, '''Replacing use of popitem() with "del self[next(OrderedDict.__iter__(self))]" removes the KeyErrors and the structure otherwise works fine.'''

(1) https://github.com/mailgun/expiringdict/blob/master/expiringdict/__init__.py