Riddle-maps (idea based on "song-maps" that the old time Maori people used to describe journeys).
Basically sage-type person translates a song-map that someone earlier had written down in its original form. Lots of scope for errors. It's a translation so no need for poetry. Sage identifies one point in song as being nearby and wants the map followed. Fit into your world. The characters can only "see" what you describe so very careful descriptive work is necessary but red herrings can be fun.
An example of full riddle map. "here the VALATAS people live above the halls the congress of tide and land, thence two noon suns cross your face and take you to the silver path. Up the path you onward go past three cold threads in summer still, then into the shadows of RAMATIS realm till the path is crossed at the weeping rock. Shortly the path splits at last, so turn your face and walk two sunsets till RAMATIS greets with open arms again. The laughing braid just in the shades, leads high to towers of earth, and there above the last falling tears, find the gates of night. No moon to light the halls of night but ochre stars will mark a path to those who walk in here. Pity you who have no meat to sacrifice to the Old Ones hidden within. Once met and your offering received dash for life to the halls of teeth. Beyond there lies the ribbon of red, rushing fast to meet the sun again, then bounding down past flaxen steps, to greet the ghost in its bed of gold."
Translation: Capitalized bits are phonetic translation of unknown words. The sage has identified VALATAS so begin here.
The party walks towards the noon sun for 2 days and finds... GM: "Towards end of second day you climb to top of ridge and look down on large river valley with the river glistening in the sun."
Following it upriver past three side-creeks that would wet you even in summer you get to woods. RAMATIS is the old people's God of forests but the PC's or sage wouldn't know this. They should easily guess though when you announce forest in the way. The river hits a gorge and a crossing is forced where a waterfall comes down a cliff face. After that the river divides at two big tributaries and you take the west one for two days. Should encounter woods again...however, the puzzle can be sharpened by woods that are no longer present (keep talking about NEW building in the area - ruins of a saw mill ??? etc). A quick flowing tributary is traced up into the mountains and above the top waterfall is a cave mouth. A path through the cave is marked by ochre crosses on the floor but it is also the lair of monster worms that fall on any meat. The travellers of old would carry a sheep up and run like hell for the cave of stalagmites (which block the worm) while it is devoured. Hope the PC have something ready...torch light will shortly show an underground river flowing the other way (no more ochre) which will lead to high mountain basin. Geologically an inlier of gold-bearing basement capped by limestone. Problem - it exits over a sheer bluff and the rope ladder has long since rotted away. The creek joins a larger creek with the disconcerting habit of disappearing an hour or two after rain (the "ghost") leaving a dry bed. And yes, this is based on real place in NZ. The creeks are gold-bearing if PC ready to dig for it the hard way. Remnants of digging all over the show.
You get the general idea. Quite a bit of work and you can lead characters by the nose through it if so inclined. Mis-translations can also help.