> The intuition that such a thing is "too powerful" is actually a pretty bad intuition here.
I still disagree. Just focus on theorem proving and not the examples that are too simple. If the halting problem could be solved, we'd be able to magically solve all these "impossible" problems. But our intuition is that just doesn't make sense, it's "too good to be true", "the universe is just more complex than that", etc. This intuition isn't a proof, but since we do have a proof, it makes sense as an intuition. That's all that's being said.
Scott Aaronson has a similar sentiment about P =/= NP:
"If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett."
Certainly not a proof -- and ofc we have none in this case -- but still a powerful intuition.
The examples matter for the correctness.
This example is a little flawed, but go with me. Imagine someone was making an argument that an algorithm is too powerful because it can solve really hard problems, then list a bunch of problems that need ridiculous amounts of compute time to solve, but half their examples are NP-hard and half their examples are P.
The intuition that says "wow, that problem is very difficult to solve, so I'm very skeptical of a solution" is wrong. Because that intuition applies to both the NP examples and the P examples. That intuition is too simplistic and overgeneral.
You need an intuition that is right with both classes of problem. It has to say "no" to one class and "yes" to another. Ignoring the wrong examples is not how you evaluate an intuition.