But that's just because of bad programming, not because of OOP, I think. I mean, of course you can use OOP to make really crappy designs, but polymorphism should make you able to have N+M implementations and not M*N.
(Static) polymorphism is the very thing behind the STL. In order to decouple algorithms from data structures, you need a standard interface between them. In the case of the STL, that interface is iterators; other interfaces (such as stacks or ranges) are also possible, and in my experience much nicer to work with. But none of it requires OOP.
Well, of course OOP isn't required for a good design. What I'm saying is that, as far as not redefining functionality for different types, it doesn't work against it. At least not if we allow for static polymorphism, and I'm pretty sure that's considered an integral part of object orientation; at least I remember Kay talking about it.
Static polymorphism wasn’t part of OO originally; in Smalltalk, everything was late-bound. And you can of course write things generically even in the “classes and methods” kind of OO, but I think the culture around that paradigm encourages coding non-generically. You might say OO itself works toward genericity, but some OO-branded languages work against it.
Coupling N algorithms and M structures may lead to M * N implementations where you really want only N + M implementations.
Additionally, decoupling algorithms and structures will probably make you write better interfaces for your structures.