Sometimes it still amazes me to contemplate that this proverb was invented at some point(...) to me this phrase sounds like a sheer background axiom of existence.

Because "the map is not the territory" is applied atheism. To a theist, the map in god's mind caused the territory to happen, so that map is even more real than the territory. And every human map is as accurate as it approaches the primordial divine map, the fact that it also happens to predict the terrain merely being a nice bonus. Even Einstein believed this. To invent "the map is not the territory" you not only need to be an atheist, you need to be an experienced, confident atheist who can figure out what follows from it, and have balls of iron to challenge about one and half millenia of intellectual tradition which was about looking for the primordial map.