Yes I am sure.  Please see the previous reasoning.  Igoring assigning to __bases__ for the moment...

Every class deletion will try to remove itself from the list.  Either it will 
a) find an existing reference in the weakref and remove it
b) find a None in the weakref and remove it.

b) is guaranteed to be the old weakref, because every previous class removal has also succeeded.  At any time, there is at most a single stale weakref in the list.

And _even_if_ there is a flaw in the argument, every call will remove _one_ stale (or just about to become stale) weakref from the list.  Whether it is its own weakref or that of a previous deletion is immaterial.  The removal of _one_ entry for each class deletion keeps the list at its optimal size.

For the case of assigning to __bases__, of course, the weakrefs are not stale and we must find the correct class to remove for correctness.

I don't want guaranteed O(1) behaviour, just O(1) for the common case of creating a class, or a few classes, and then removing them.