The main obstacle to overcome here is to make a system introduces as little repetition/redundancy as possible.

Even if I go around and custom-make 50 treasure maps, after doing roughly 50 maps you will start to see repeats. With something like this, it completely ruins the fun. So this route would be the last resort. It will take the most manpower and in the end eventually will defeat the purpose.

The ideal way would be to randomly generate the maps. While this wouldn't take the same amount of manual workpower, it will be difficult to do so in a fullproof way. I would need to somehow figure out a way to determine what areas are accessible to players and what areas aren't. I couldn't risk a player getting even one map that they can't reach, as the entire point is to guess where it is... if players can't guess, even if it is legitimate(ie reachable) they may start to assume it isn't, and they got a dud. Not to mention if it's random there is no way to determine the "difficulty" of said maps. It may generate an obvious treasure map that can be instantly guessed, and when you're doing random rewards it means the rewards may not be proportionate to the effort.

Tricky tricky.