You're totally correct: The goal is to find the right abstractions. Bad abstractions keep getting in your way either by leaking too much or by being based on invariants that turn out to be not actually be all that invariant, whereas good abstractions have no need to be touched again later.
For me, the additional layer of "how hard is it to change the abstraction if it turns out to be wrong" is also quite important. In my environment (algorithmic R&D) you never quite know which invariant your next idea will break. And this is where OOP can really bite you - untangling code from a class hierarchy or twisting interfaces to bend to your new ideas is anywhere between infeasible and a complete mess. Composition over inheritance can help save a lot of frustration here. But sometimes interface/abstract base class + a single implementation also provides a very clean abstraction to separate the core model/algorithm from the fiddly details. Just don't fall for deep hierarchies or large interfaces would be my takeaway so far.
Maybe we just need to get better at giving up on abstractions when they fail? I think that's very tough because they tend to still dictate how we think about problems (plus the usual cost of rewriting code). Your approach of delaying the abstraction choice sounds very interesting (somewhat akin to Extreme Programming?), I will try to keep that in mind for the future. In thinking about this I'm mostly afraid of code sort of remaining at this "makeshift"/provisional level and never actually settling into something more organized (due to lack of incentive/time to improve it). I think that can be kept under control, but do you have any suggestions on that front?