All this talk about encounter tables, and we’ve overlooked what some might consider an important detail: where do all these critters actually live in your setting? 
This is a big issue in terms of setting development, and it requires you to make a decision about planning ahead or doing stuff on the fly. As an advocate of the less-is-more approach, which describes your setting via game tools instead of narrative, I want the encounter tables to do as much of the heavy lifting as possible.
The idea is to populate your setting via your random encounter tables. You’re going to create these tables anyway, and a combination of nested and dynamic tables does a great job of helping you describe your setting’s inhabitants and what they do.
But where they live is a different matter. Sandbox tradition demands that you populate your map with a number of fixed encounters, which occur when players visit them (or arrive in the hex containing them), then allow for random encounters as if they were merely wandering monsters. I’m suggesting that you populate your map with fixed encounters created via the random encounters tables. 
Creatures don’t exist until they’re encountered, so you can put rare and unique stuff on the table, even if you don’t really “envision” it as being part of your setting. In fact, it’s not, until it’s encountered, at which point, you have a major campaign event in which something from the realm of fairytales and folklore is suddenly determined to be real. [Emphasis mine.]
This is S-M-R-T: Smart. FrDave’s approach gives you license to create encounter tables with any monster you might like to have in your setting. By subtle extension, monsters have no fixed lairs until they’re encountered, which is a exactly what we need for the dynamic, less-is-more approach.
Dynamic Monster Territory
Two assumptions: (1) you’re mapping on a regional hex template of 125x125 miles, broken into 5-mile hexes, and (2) all monsters have a home, or at least a semi-permanent lair where they eat, sleep, and make little monsters.
When a monster is encountered, you can assume that the encounter occurs in the monster’s home territory, the range of which is roughly proportional to the creature’s size. Ordinarily, this territory is defined as some neat and tidy radius surrounding the monster’s fixed lair. But that really only works if you’re planning ahead by placing fixed lairs and territorial borders on your map. We’re not doing that.
Instead, we’re populating the map via random rolls, which may or may not indicate the presence of an actual monster, whose identity we don’t know until the roll is resolved. So while we can assume that an encounter occurs inside a monster’s territory, we don’t know how big that territory is or where its lair is in that territory.
Percent in Liar
Time for another tweak to the encounter table. Next to each monster, we’ll add a Range value:
This is the size of the monster’s territory in 5-mile hexes, based on monster size:
Smaller than Small: 0-3 (1d4-1) hexes
Small, Medium, or Large: 0-7 (1d8-1) hexes
Bigger than Large: 0-11 (1d12-1) hexes
You’ll note that these values are not only smaller than those suggested in Monster Turf, but also variable in size. This is intentional, and ultimately gives you the flexibility to account for more monster lairs in the available space of a Regional Hex map.
Here are some optional (cumulative) modifiers to the range’s size:
Monster is especially territorial or an apex predator: +1 hex
Monster is a flyer or can travel great distances with ease: +2 hexes
Monster is solitary: -1 hex
Monster is unintelligent: -1 hex
Monster is subterranean: -2 hexes 
For our purposes, the minimum range value is zero (0) hexes.
The territory can be any shape but the hexes must be continuous. This means that the territory may include sub-optimal terrain for the monster, or that it might overlap the territory of another. Naturally, either possibility can suggest a monster’s motivations during the encounter.
The range value not only determines the size of the monster’s territory, but can also suggest how far away it is from its lair. A range of zero (0) means that the lair is in the hex where the monster’s encountered. If the range result is the maximum for the die, then the monster is expanding its borders and is on unfamiliar ground (and possibly lost). For values greater than zero but less than the maximum, assume the lair occupies the most optimal terrain in the territory.
There is one consequence of this approach: Your setting will get crowded over time, as more random encounters end up creating more territories and lairs.
But this actually makes sense. Monster populations will change over time, especially with adventurers rampaging about. The PCs might encounter trolls, track them to their lair, and (if they can destroy them) revert the troll’s territory to wilderness... where something else (via another random encounter) is bound to move in. 
Let me know if this makes sense to you, and what you’d change to make it better.
Which is not to say that you can’t deliberately place some fixed lairs or settlements—by all means, drop a human town here or a giant bee mound there. The goal here is simply to let the encounter tables populate the areas you haven’t figured out.
Subterranean monsters have underground territory, but may have access to the surface through one or more hexes.
And the resulting need to be ever-vigilant against chaos, monsters, blah, blah, blah, is what keeps adventures motivated, busy, and paid. If monster territories operate as a revolving door, you'll always have a source of adventure hooks to give the PCs something to do.