As there seem to be some geocachers here - I have another idea for an arduino-powered traditional geocache.
I'd love to do this myself, but since I'm in the middle of a big city I can't find the right spot to pull this off anywhere near me where I could maintain it.
Here's the idea:
You make a plastic cache-container that can close with a servo from the inside like my reverse geocache. You'll add an arduino, some kind of display mounted in the lid and an rfid reader with the antenna on the bottom of the container. For power supply I'd add a 9V battery holder that can be accessed from the outside.
Then you hide the cachebox in a place from where you can see two distinct landmarks (a bench, some kind of tree stump, etc.). In the cache listing you'll tell the people to bring a 9V battery.
When the cacher finds the cache it won't open. They insert the 9V battery and the display says 'put me on the red mark on the bench behind you'.
There's an rfid card glued under that spot and when the cacher puts the box there the reader sees the rfid and the display says 'Put me on the treestump 200 meters north of here - you have 50 seconds... '. A countdown from 50 begins.
If the cacher does't put the box on the rfid chip in the tree stump within the 50 seconds he has to start over (put it on the bench). If he makes it the box says 'Now back to the bench, you got 45 seconds' 
and the countdown starts.
If he makes it back to the bench in time the box opens. To close it again he has to take out the battery and put it in again or put the box on a third rfid chip.
Would be real fun if you would install that somewhere where you could watch the people running around
You could also add more rfid stations or make them run faster.
[edit]
If you find a spot where there's something like a grid with different field on the ground (like these giant chess boards in parks) you could also make out a kind of puzzle where you have to place the box on different fields with rfids buried in them due to hints on the display. Like just displaying 'A3-D5-F3' with the chess board.
[/edit]