I think the main problem with OOP is that the classic animal/cat/dog type class hierarchy examples that are used in teaching are in fact hardly ever used in the real world - giving a very misleading view of how it's actually used in practice.

Most people using OOP languages prefer composition over hierarchies and I almost never see those complex class structures modelled on data ( for some of the reasons you give ).

In terms of evolvability - encapsulation - a key feature of OOP - is a key tool in enabling that.