In designing the wilderness area for my Greyhawk campaign, I'm finding that I have a million and one choices to make as to my "wilderness procedures", and that these will shape a) how I prepare my material, and b) how smoothly the game runs when we're in the thick of it.
It all comes down to encounter checks (of several varieties). In order to capture the level of simulation (and risk vs. reward) I'm looking for, I'm going to have time-based encounters (as per the DMG - checks at predefined intervals during the day) and exploration-based encounters (1 check for every new hex entered, probably a 1 in 6 or a 1 in 10, with the chance for encounter increased in dangerous hexes like mountains and forests). Exploration checks will draw from nearby lairs (with a chance to find the lair itself based on "% in lair"), while time-based checks will be from a terrain-based encounter table (and may add new lairs to the map, again depending on the "% in lair" rolled). Encounter checks within a few hexes of settlements will have a chance of being converted into a "patrol" encounter (which may or may not benefit the PCs, depending on what they've been up to lately), while encounters on a road or frequently-traveled trade route will use a dedicated "on the road" encounter table (which itself contains a certain chance of monster encounters).
I'm also splitting "creature checks" (monsters, travelers, patrols, etc.) from "location checks" (ruins, relics, settlements, etc.). Passing through a hex, I'll roll a "chance to spot" for each listed (and previously undiscovered) ruin or relic in the hex (setting this on-the-fly - something small but in the open would be a 1 in 6, something big a 2 in 6, a settlement 3 in 6 assuming it's out in the open, while something concealed might be a 1 in 8 or 1 in 10). Searching a hex will take as long as crossing the hex twice, and will allow another roll to spot (with the chance to spot improved by 1). If the PCs spot nothing (or they've already discovered everything in the hex), I'll roll a 1 in 6 chance to discover something new (taken from a pregenerated list of unassigned R&Rs) and add it to the hex. (I expect frequently-traveled wilderness routes will become quite detailed as the campaign matures.)
Now, I know the chances to spot something in an actual 25 square mile area are miniscule, but this is a game conceit I'm willing to live with. I'm generating between 1 and 3 locations for each hex on my initial pass-through - it's to be assumed each hex contains many more than this, and that the others will be added on subsequent passes (once the pregenerated ones are discovered). This is all conjecture until it actually sees play, of course - I'll hopefully get to try it Tuesday, and I'll check in to report how it goes. I'm aiming to have three full "Darlene hexes" (the 30-mile hexes from the folio map) detailed at "Wilderness Grand Tactical" scale (5-mile hexes) by then, and I'll let the players know that if they get off that map, then the FPS (fights per second) of the game is going to slow drastically (while I whip up new crap).