Let's see if I can provide a very rudimentary intuition about why this might happen. YMMV, and I'm sure this isn't the whole story.
O(n^2) basically implies that we have to look at every pairwise combination of elements. Higher powers might imply needing to look at combinations of multiple elements / paths / whatever. In practice, these algorithms tend to be more or less tractable.
O(2^n), on the other hand, generally implies a brute force search, where we need to consider every possible solution, or every possible combination of elements. This is essentially the same as saying we can't do much better than guesswork.
So O(n^k) versus O(2^n) is basically "looking at small groups of elements of known size" versus "trying every possible solution."
This isn't the whole story—there are problems in between the two groups, though a couple of big ones have been reduced to polynomial time in recent years. But to understand the "metaphysical" interpretations that some CS people sometimes loosely apply to the two classes, it helps to look at the actual distribution of real world algorithms. It's pretty clumpy. There's an empirical element here.
Such is the case with P and the notion of being "easy" to compute. Yes, some algorithms in P are actually qualitatively "hard" and some outside are actually qualitatively "easy". But in the vast majority cases, finding that a problem is in P means we've drastically reduced its difficulty, and proofs that a problem isn't in P establish bounds that make it unfeasible in the general case.
The only thing I am criticizing here is the _metaphysical_ implications of computational complexity classes (and also, jargon which is misleading for not TCS people - e.g. O(n^100) s not "efficient" or "fast"). Furthermore, as you pointed, some problems have practical solutions which usually work efficiently, even if not always or give approximate, but still - useful, solution.
> There have been plenty of results that stand to be very physically relevant
What I meant was not "can be applied to physical systems" (I agree!), but "is a foundation for physical laws" (I am highly skeptical and I am yet to see an example).
(Though, to be honest, I was more in quantum info that quantum computing; and right now I am more into... quantum JavaScript: http://quantumgame.io/)