This would break Python's consistency.  'not' of a value returns its boolean inverse, and the boolean value of NotImplemented is True, just like the boolean value of any object that does not have methods that set its boolean value is True.  Having anything that is True return True when not is applied would be even more perverse than NANs are :)

The correct implementation of your __ne__ method is to not define it.  Python will then do the 'not __eq__(other)' call itself.