> As it stands, calling Element.__deepcopy__() will succeed with the C
> implementation and fail with the Python implementation.

You should not call it directly. Use copy.deepcopy().

> What is
> different about the C implementation that requires the definition of
> __deepcopy__() in the first place?

__deepcopy__() in the C implementation is merely optimization. It is less efficient to convert from the efficient internal representation of Element object to tuples and dicts and back.

> However, create_new_element()
> does not make a copy of the attrib dict that is passed in, meaning that
> the internal attrib dict of an Element instance is mutable by changing
> the dict that was passed in.

create_new_element() usually is called with a new copy of the attrib dict. Making yet one copy inside it is just a waste of time. If in some cases it is called with an externally referred dict, fix these cases by making a copy before calling create_new_element().