> do we still only support single inheritance at the C level?

Not any more. Heap types may have multiple bases, and they can be created at the C level (since Python 3.2, PEP 384).

>  So, I think we should do something like walking up the hierarchy to find the C function in it that is currently being called, and then check if it's the one we would expect or if a subclass defines a different one. The current check does not bother to search and just assumes that it knows which (super)type defines the right function to call.

Should we be bold and skip the check for heap types?
That would mean that when/if `str` is converted to a heap type, you could do `object.__delattr__(str, "lower")`. That would break your Python, but only at the Python level (similar to things like `import builtins; del builtins.__build_class__`).
Heap types are not shared between interpreters, so that reason is gone. But Guido's [2003 mail] suggests there are other reasons to prevent changing built-in types. What are they?

[2003 mail] https://mail.python.org/pipermail/python-dev/2003-April/034535.html