Let the player find the first cache that contains some items as well as a piece of paper with a riddle on it, solving the riddle leads the player to the next cache, which contains a little better item and another riddle to the, yet another cache... so the loot becomes better and better as the player solves the riddles.
to prevent the player from getting the riddles solved from the internet, the devs can pick like 200 locations in the map, give each a riddle that describes its location, and while a new game initializes it randomly generates a sequence of geocache of, say, 10 caches. that way every time you play the game you get different caches.
Choosing 10 out of 200 is like, C(200, 10) = 200! / ((200!)(200-10)!) = 2.24510043090133e+16 different ways of playing the geocache game!!! that's like 400,000.
how do you think? It should be very easy to implement... just come up with the riddles and place the cache in the game!