WeakKeyDictionary has some bugs
Created originally on Bitbucket by kmod (Kevin Modzelewski)
It looks like PyPy uses the CPython implementation of WeakKeyDictionary and WeakValueDictionary, but that implementation relies on quick destruction. It looks like PyPy (2.6.0) has a fix for the WeakValueDictionary case, but WeakKeyDictionary has the same issue (the callback can be postponed to the point that it removes the wrong entry from the dict).
Here's Pyston's solution (and corresponding test), which I think should work for PyPy but I haven't tested it: https://github.com/dropbox/pyston/commit/28dc1184d7b2178df4e9bc00ae2e1eaffea575f9