copy.deepcopy()-ing a tree structure that has internal parent and cross-reference links implemented as weakref.proxy() objects causes the weak reference proxies themselves to be copied (still refering to their original referents) rather than weak references to deep-copied referents to be created.

A workaround is to add the following __deepcopy__ method to affected classes:
    def __deepcopy__ (self, memo):
        # taken from Stackoverflow: "How to override the
        # copy deepcopy operations for a python object"
        # and "Python: dereferencing weakproxy"
        cls = self.__class__
        result = cls.__new__ (cls)
        memo [id (self)] = result
        for k, v in self.__dict__.items ():
            if isinstance (v, weakref.ProxyType):
                new_v = weakref.proxy (copy.deepcopy (
                        v.__repr__.__self__, memo))
            else:
                new_v = copy.deepcopy (v, memo)
            setattr (result, k, new_v)
        return result

If you deep-copy the referents, what would hold a reference to them? Wouldn't the new objects be immediately GCed?

Well, in the example code, the memo dictionary contains the (hard) reference to newly created objects but ultimately, at the close of the deepcopy, the objects are (hard) referenced using the normal "child" attributes.

I don't however know how this would work if this was implemented within the weakref code but I expect that their __deepcopy__ method also has access to the memo variable.  If, at the close of deepcopy and the destruction of memo, no (hard) references exist to an object, then it would be collected, but that matches standard weak reference semantics.

Even if it were not possible to solve this programmatically within Python, I think the problem (and e.g. the workaround given below) should be mentioned in the documentation of deepcopy and/or weakref.