Blair:  I don't think you'll have any problems getting the behaviour you in Python 3.  For example:

Python 3.2a0 (py3k:77952, Feb  4 2010, 10:56:12) 
[GCC 4.2.1 (Apple Inc. build 5646) (dot 1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> class xcomplex(complex):
...     def __add__(self, other): return xcomplex(complex(self) + other)
...     __radd__ = __add__
... 
>>> xz = xcomplex(1+2j)
>>> all(type(xz + y) is type(y + xz) is xcomplex for y in (1, 10.0, 10+1j, xz))
True

So I don't consider that the removal of coerce and the __coerce__ magic method is a step backward:  it still allows mixed-type operations, but without coerce the rules for those operations are significantly cleaner.

The real problem case in 2.6.4 seems to be when doing <instance of complex> + <instance of xcomplex>:  in this case, Python first calls complex.__coerce__ (which returns its arguments unchanged), then complex.__add__.  None of the xcomplex methods even gets a look in, so there's no opportunity to force the return type to be xcomplex.

If you look at the source (see particularly the binary_op1 function in Objects/abstract.c ) you can see where this behaviour is coming from.  The complex type (along with its subclasses) is classified as an 'old-style' number, while ints, longs and floats are 'new-style' (note that this has nothing to do with the distinction between old-style and new-style classes).  Operations between new-style numbers use the scheme described in the documentation, but where old-style numbers are involved there's an extra coercion step.  In particular, when adding a complex to an xcomplex, the rule you quoted (about the case when the right operand is an instance of a subclass of the class of the left operand) isn't applied.

It's too risky to change the general behaviour for old-style numbers:  I don't think there are any old-style numbers besides complex in the Python code, but there may well be some in third party extensions.  Certainly documenting it better would be an option, and making complex a new-style number for Python 2.7 seems like a reasonable thing to consider.