[Guido van Rossum]
If I remember well, the only destructors not called would be __del__ methods, since the dependencies between to-be-deleted instances are unknown to the collector. Regular (C-level) destructors would of course be called.
Seems to me that the dependencies among to-be-deleted arbitrary C objects are equally unknown to the collector. Assuming there's a fundamental difference between objects implemented in Python and objects implemented in C seems shaky on the face of it. Or if it's not just a convenient assumption, on what is it based?
My assumption was based on the standard Python objects. Cycles necessarily have to include dictionaries or lists (modules, classes and instances link to each other through dictionaries; ditto for function objects; i'm crossing my fingers here for stack frame and traceback objects :-) and I can do things to these to get rid of the links without getting rid of the objects: del L[:] or D.clear().
Third party C objects might have interdependencies similar to those found in Python instances, but my gut feeling is that these aren't as problematic -- e.g. interdependencies between C modules are rare (because the machinery is cumbersome) while they are common between Python modules; and C code isn't susceptible to the problems that Python destructors encounter when the modules they import have already been destroyed.
I know, it's an unusual amount of handwaving...
--Guido van Rossum (home page: http://www.python.org/~guido/)