Maybe you could combine something like that with the way contracts are done? Have the contractor give you directions on how to get there where you need to go, but no actual target is shown on the map. Then you can go look for it yourself or buy the information from someone. You could even turn it into something of a quest line with you having to go find the right information broker for hard to find locations. Would add an opportunity for exploring, while also providing a natural alternative to it.
