NotImplemented is a speed and maintainability hack - the runtime cost and additional code complexity involved in doing the same operator signalling via exceptions would be prohibitive (check Objects/abstract.c in the CPython source if you want the gory details).

As far as an implementation of @total_ordering that correctly handles NotImplemented goes, yes, I absolutely agree we should do this correctly. The fact that it is *hard* is an argument in *favour* of us getting it right, as there is a decent chance that manually written comparison operations will also stuff it up.

That said, I don't think sane_total_ordering quite gets the semantics right, either.

Some helper functions in the closure would let the existing lambda functions be updated to do the right thing (and I believe the semantics I have used below are the correct ones for handling NotImplemented in @total_ordering). (I haven't actually run this code as yet, but it should give a clear idea of what I mean)

def not_op(op, other):
   # "not a < b" handles "a >= b"
   # "not a <= b" handles "a > b"
   # "not a >= b" handles "a < b"
   # "not a > b" handles "a <= b"
   op_result = op(other)
   if op_result is NotImplemented:
     return op_result
   return not op_result

def op_or_eq(op, self, other):
   # "a < b or a == b" handles "a <= b"
   # "a > b or a == b" handles "a >= b"
   op_result = op(other)
   if op_result:
     # Short circuit OR, as op is True
     # NotImplemented is also passed back here
     return op_result
   return self.__eq__(other)

def not_op_and_not_eq(op, self, other):
   # "not (a < b or a == b)" handles "a > b"
   # "not a < b and a != b" is equivalent
   # "not (a > b or a == b)" handles "a < b"
   # "not a > b and a != b" is equivalent
   op_result = op(other)
   if op_result:
     # Short circuit AND, as not_op is False
     # NotImplemented is also passed back here
     if op_result is NotImplemented:
       return op_result
     return not op_result
   return self.__ne__(other)

def not_op_or_eq(op, self, other):
   # "not a <= b or a == b" handles "a >= b"
   # "not a >= b or a == b" handles "a <= b"
   op_result = op(other)
   if op_result is NotImplemented:
     return op_result
   if op_result:
     return self.__eq__(other)
   # Short circuit OR, as not_op is True
   return not op_result

def op_and_not_eq(op, self, other):
   # "a <= b and not a == b" handles "a < b"
   # "a >= b and not a == b" handles "a > b"
   op_result = op(other)
   if op_result is NotImplemented:
     return op_result
   if op_result:
     return self.__ne__(other)
   # Short circuit AND, as op is False
   return op_result

The conversion table then looks like:

convert = {
  '__lt__': [
    ('__gt__',
      lambda self, other: not_op_and_not_eq(self.__lt__, self, other)),
    ('__le__',
      lambda self, other: op_or_eq(self.__lt__, self, other)),
    ('__ge__',
      lambda self, other: not_op(self.__lt__, other))
  ],
  '__le__': [
    ('__ge__',
      lambda self, other: not_op_or_eq(self.__le__, self, other)),
    ('__lt__',
      lambda self, other: op_and_not_eq(self.__le__, self, other)),
    ('__gt__',
      lambda self, other: not_op(self.__le__, other))
  ],
  '__gt__': [
    ('__lt__',
      lambda self, other: not_op_and_not_eq(self.__gt__, self, other)),
    ('__ge__',
      lambda self, other: op_or_eq(self.__gt__, self, other)),
    ('__le__',
      lambda self, other: not_op(self.__gt__, other))
  ],
  '__ge__': [
    ('__le__',
      lambda self, other: not_op_or_eq(self.__ge__, self, other)),
    ('__gt__',
      lambda self, other: op_and_not_eq(self.__ge__, self, other)),
    ('__lt__',
      lambda self, other: not_op(self.__ge__, other))
  ]
}