Agreed about fixing the other issues. I'm still unclear that we need anything more than just the _remove_dead_weakref function to do that, but also, I don't see a particular problem with adding self._commit_removals() a bit everywhere.
About the O(1) expectation for len(): it's still unclear if it is better to give a precise answer or if an over-estimate is usually enough. I can see of no reasonable use for a precise answer---e.g. code like this
while len(d) > 0:
do_stuff(d.popitem())
is broken anyway, because a weakref might really die between len(d) and d.popitem(). But on the other hand it makes tests behave strangely. Maybe the correct answer is that such tests are wrong---then I'd be happy to revert the PyPy-specific change to __len__() and fix the test instead. Or maybe weakdicts should always raise in __len__(), and instead have a method .length_upper_bound().