One of the things that prompted the OP was this breakage in Python's cryptography package [1] (OP actually opened this issue) due to the introduction of a Rust dependency in a 0.0.x release. The dependency change didn't change the public API at all, but did still cause plenty of issues downstream. It's a great question on the topic of semver to think about how to handle major dependency changes that aren't API changes. Personally, I would have preferred a new major release, but that's exactly your point syllogism — it's a matter of opinion.
As a sidenote, Alex Gaynor, one of the cryptography package maintainers is on a memory-safe language crusade. Interesting to see how that crusade runs into conflict with the anti-static linking crusade that distro packagers are on. I find both goals admirable from a security perspective. This stuff is hard.