I think the issue of __len__() is a different matter.  More below.

>> The C function would simply call PyObject_GetItem() and
>> PyObject_DelItem()---without releasing the GIL in the middle.
>
> If you implement it like that, and the dictionary has non-trivial
> keys with a user-defined __hash__, then the GIL can be released
> at the beginning of PyObject_DelItem().

Right, I see your point: your version will, in any case, remove only a dead weakref as a dictionary value.  +1

Now about __len__() returning a wrong result: it is a more complicated issue, I fear.  I already patched weakref.py inside PyPy in order to pass a unit test inside CPython's test suite.  This patch is to change __len__ to look like this:

    def __len__(self):
        # PyPy change: we can't rely on len(self.data) at all, because
        # the weakref callbacks may be called at an unknown later time.
        result = 0
        for wr in self.data.values():
            result += (wr() is not None)
        return result

The problem is the delay between the death of a weakref and the actual invocation of the callback, which is systematic on PyPy but can be observed on CPython in some cases too.  It means that code like this may fail:

     if list(d) == []:
         assert len(d) == 0

because list(d) might indeed be empty, but some callbacks have not been called so far and so any simple formula in __len__() will fail to account for that.  ('issue28427-atomic.patch' does not help for that, but I might have missed a different case where it does help.)