I somewhat agree with the state, if it costs money to manage the lands, the people who front those costs get priority over those who don't.
I also agree with the idea to make Geocaching a season, just like any other hunting season. If the lands are paid for by hunting licences, then raise revenue by selling Geocache licences during the Geocache season.
Searching for Geocaches could be $15-$20 for a statewide seasonal permit (minors are free). The permit could also allow you to hide 1 registered geocache to limit how many are placed. Instead of simply shutting the door on an entire hobby, just monetize it. Duh?
As a person who also loves to play paintball, that should be a permanent ban. Paintball should only be played on private fields where the owner doesn't care if his woods are torn up. There is no way to play that game in the woods and have limited impact on the enviornment. You just can't.