They're definitely not immune to No Free Lunch, but they are able to predict Perlin noise.

(Sure, you could try to analyse humans as if they were spherical objects floating in void, but in practice humans have computers.)

Let me give you an example. The 2011 Nobel prize in chemistry was dedicated to the discovery and analysis of quasicrystals. Those also cannot be modeled by deep learning, as its building blocks, linear separators, cannot finitely appreciate infinitely generated structures (unless it essentially encodes a completely different ML system within its neural network). Yet humans can model them.

I could go on all day about this, as there is an infinity of problems where deep learning is inadequate: proving the three-color theorem, routing, computing multiplications, …

Don't get me wrong: deep learning is outstanding for a set of menial tasks that I love to see being handed off to machines. But it is not the be-all, end-all that is sometimes claimed.