I have been thinking about random wilderness encounters in my Barbarian Conqueror King setting. What I have in mind is vary the encounters according to area type (Civilized, Borderland and Wilderness) not only by the chance of encounter, but also by the difficulty of encounter; close to civilization, patrols and high-level NPCs have already killed off the more dangerous foes in most cases, while in deep wilderness the worst monsters run free unchecked. Also, I might divide the Regional Map into areas (say, the Harat Swamps and so on), each several hexes in size and each having its own flavoured encounter table. This will also allow for certain areas to become (in)famous for their monsters, such as “Beware the T-Rexes of the Great Northern Forest” or “The Harat Swamps are notorious for their Giant Toads”.
I’ve been meaning to do the same thing for my Crimson Sun setting, and I think it’s almost essential for differentiating a region. I’ll probably expand it beyond just random encounters with creatures, to include environmental hazards and odd sights typical to the region.
So, for instance, the Obsidian Plains, the Great Alluvial Sand Waste, the Ringing Mountains, and the Forest Ridge will all have their own encounter tables.
A bonus effect I like is that this reduces the number of “universal” monsters; I have an odd (?) dislike for monsters that are found absolutely everywhere in a setting, at least as common creatures; in a typical fantasy world, it makes sense that dragons are found all over the world, because they can fly and their territories are enormous, but e.g. rust monsters seem like something that should have a very limited range of existence - the ruins of one specific empire, for instance, or one continent’s underworld.