Yeah, this doesn't seem that bad. I mean, Scry is kindof a non-thing - anyone who seriously wants to hide their stuff is going to make it scry-proof. And if you can't scry, you can't teleport.

I don't think this is as hard as you are making it out to be. I mean, heck, comprehend languages doesn't work on codes - it specifically says so. So sure, you can't make the map a "really old map" and expect it to work, but a little bit of thinking about this stuff means it's not that hard.

So I guess the real answer is: To challenge mid-level characters, use mid-level resources. Look into the various ways that the tools mid level characters have can be legitimately countered. It's not like no one in the world has ever heard of "scry and teleport" before.