I wouldn't say issues like this are dues to irreducible complexity, but more symptomatic of long-lived languages that continually get extended but don't give up on backwards compatibility. It's basically the 2nd law of thermodynamics applied to programming languages that they will eventually die due to increased entropy.

Maybe if move semantics, and noexcept, had been designed into C++ from the beginning then the designers might have chosen to insist that move constructors be noexcept, but since these were added later there is code out there with move constructors that do throw exceptions...

Note by the way that the issue being described isn't strictly about std::move or move semantics in general, but more about the STL and containers like std::vector that have chosen to define behavior that makes noexcept move constructors necessary to be used when reallocating.