I had permission to a bunch of adjacent farm/pasture/bush land near a school I worked at. I think this would be reasonable also in utility type public land: community pasture, national forest, wilderness areas, but not in lands whose function is beauty such as parks, or sites that get large traffic flows.
We had an orienteering game that ran in winter. Because it was in winter, I had to have all the controls set up before snow fall. Because I had to adjust the spread of the game depending on how deep the snow was, I needed 3 times as many controls as I expected to use. Because kids were in the school for 3-5 years I had to be able to go that long without reusing a control point.
What I did was to make controls out of 4" squares of UV resistant coreplast. These were affixed to a tree or fence post with a roofing nail, on the north side. I wrote on the squares with an artline 400 paint pen, AND a laser printed Avery weatherproof label.
Each square had an ID and a codeword. E.g. ID A21 Codeword Rambunctious Rhino.
Directions as to how to get there referred only to the ID. Return with the codeword proved that they had been there.
Clues generally had two components: Part one got you to the general vicinity. Part two told you what to look for. So a simple one would be 721 654 using the standard UTM grid. That is accurate to 100 meters. Part 2 would be something like: "Double trunk birch near hill top" More complex ones could depend on plotting bearings from landmarks, figuring out how to do some form of search, doing research on the internet.
If you were making a game for one use, you could skip the nails, and use baling twine. Or you could just write on flagging tape.
At the end of 5 years I had over a thousand controls, spread out over 200 km2 of territory, all with gps coordinates to within 5 meters. In the fall I would take a map of a zone, usually a square mile, and would spend the day checking previous controls and adding new ones if I was inspired to some clever new clue.
The school is not open any more. But a description of the game, and how it works is here:
http://rogaine.sherwoods-forests.com/