I like Nick Coghlan's suggestion in msg140493, but I think he was giving up too soon in the "or" cases, and I think the confusion could be slightly reduced by some re-spellings around return values and comments about short-circuiting.
   
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 NotImplemented
    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 is NotImplemented
        return self.__eq__(other) or NotImplemented
    if op_result:
        return True
    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 is NotImplemented:
        return NotImplemented
    if op_result:
        return False
    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 self.__eq__(other) or NotImplemented
    if op_result:
        return self.__eq__(other)
    return True

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 NotImplemented
    if op_result:
        return self.__ne__(other)
    return False