Looking further into this issue, OrderedDict.pop() using the key returned from the KeyError (using eval(str(error))) also yields a KeyError. And OrderedDict.popitem() does not change the dictionary (so it's not like the KeyError is raised even though it worked).

Also it appears to be empty actually. list(OrderedDict) returns an empty list even though str(OrderedDict) does not. So maybe some operations do only remove entries from one part of the data so that popitem() still thinks it's in the cache. Now I'm not familiar with urllib3 so I'm not sure how that internal OrderedDict is used to narrow down what might cause that issue.

And additionally I tried to output keys(), items() and values() separately and suddenly I get a KeyError even when I just do str():

    conn = self.poolmanager.connection_from_url(url)
  File "/home/xzise/.pyenv/versions/3.6-dev/lib/python3.6/site-packages/requests/packages/urllib3/poolmanager.py", line 139, in connection_from_url
    return self.connection_from_host(u.host, port=u.port, scheme=u.scheme)
  File "/home/xzise/.pyenv/versions/3.6-dev/lib/python3.6/site-packages/requests/packages/urllib3/poolmanager.py", line 125, in connection_from_host
    self.pools[pool_key] = pool
  File "/home/xzise/.pyenv/versions/3.6-dev/lib/python3.6/site-packages/requests/packages/urllib3/_collections.py", line 66, in __setitem__
    __before = str(self._container)
KeyError: ('https', 'ru.wikipedia.org', 443)