Personally, I think this is a good case for returning NotImplemented that matches the use-case in the rich comparison.  It isn't that we have an abstract base class function we haven't overridden (which I think is the common usecase for raising NotImplementedError), but we want to send a message to the system to try alternatives.

That said, i don't have a very strong feeling one way or the other.  I have a preference for returning NotImplemented, though.