I've certainly encountered clang & gcc not finding or just not having header files a good couple times. Mostly around cross-compilation, but there was a period of time for which clang++ just completely failed to find any C++ headers on my system.

Yes, clang is famously in this category.

If you copy the clang binary to a random place in your filesystem, it will fail to compile programs that include standard headers.

A compiler that can't magically know how to find headers that don't exist in the expected directory?

Yes, that is the case for pretty much every compiler. I suppose you could build the headers into the binary, but nobody does that.