If I know that a Counter (or any class X) can be updated in place, I will be surprised to find out that I'm using a different instance after a successful in-place operation.

I would even consider that (replacement of the original instance) a security risk, though it is mitigated by the fact that I don't see how to exploit it without already being able to create arbitrary subclasses.

> For subclassing to work, the fix is:
> 
>         if not hasattr(other, 'items') or type(self) is not Counter:
>             return NotImplemented

That breaks for Counter subclasses on the left hand side -- even a trivial subclass to change the repr would fail unless the _i* methods were all re-implemented, either by the otherwise-trivial Counter subclass or by the right-hand objects.  If you start making it work for the obvious cases, you just make the failure conditions more obscure.