There’s a wide variety of “No Free Lunch” theorems proving that, in general, some problem is unsolvable. Very often, these theorems are not relevant because the real universe is a special case.
In a very general and metaphorical sense, most of these theorems say some equivalent of, “There’s no universal good strategy: For every universe where an action causes you to gain $5, there’s a different universe where that same action causes you to lose $5. You can’t get a free lunch across every universe; if you gain $5 in one universe you must lose $5 in another universe.” To which the reply is very often, “Sure, that’s true across maximum-entropy universes in general, but we happen to live in a low-entropy universe where things are far more ordered and predictable than in a universe where all the atoms have been placed at random.”
Similarly: In theory, the protein folding problem (predicting the lowest-energy configuration for a string of amino acids) is NP-hard (sorta). But since quantum mechanics is not known to solve NP-hard problems, this just means that in the real world, some proteins fold up in a way that doesn’t reach the ideal lowest energy. Biology is happy with just picking out proteins that reliably fold up a particular way. “NP-hard” problems in real life with nonrandom data often have regularities that make them much more easily solvable than the worst cases; or they have pretty good approximate solutions; or we can work with just the solvable cases.
A related but distinct idea: It’s impossible to prove in general whether a Turing machine halts, or has any other nontrivial property since it might be conditioned on a subprocess halting. But that often doesn’t stop us from picking particular machines that do halt, or limiting our consideration to computations that run in less than a quadrillion timesteps, etcetera.
This doesn’t mean all No-Free-Lunch theorems are irrelevant in the real-universe special case. E.g., the Second Law of Thermodynamics can also be seen as a No-Free-Lunch theorem, and does actually prohibit perpetual motion in our own real universe (on the standard model of physics).
It should finally be observed that human intelligence does work in the real world, meaning that there’s no No-Free-Lunch theorem which prohibits an intelligence from working at least that well. Any claim that a No-Free-Lunch theorem prohibits machine intelligence in general, must definitely Prove Too Much, because the same reasoning could be applied to a human brain considered as a physical system.
I contend that these results are “often” irrelevant. I think this may be a case of survivorship bias. You point out examples in which the theorems are side-stepped, but the side stepping was gained after most of human history was finished. They are also still unsatisfactory to researchers (NP-P isn’t even proven). There are combinatorially difficult problems everywhere. Everyday problems with relationships, jobs, business ideas, governing, are technically too hard and are pretty much trial and error. You mention humans being smart, which is true, but we are still slow to learn, and science/math/society are slow to progress despite having billions of us. Otherwise, we would be heuristicing our way to the answers of grand questions and we would have things as smart as us already.
This is interesting! Is there a name for this concept / area of thought?