Several things:
1) Once my players started building their cities, I actually de-emphasized hexploration and substituted in my own plots and/or other modules. At this point, your players aren't adventurers. They're the rulers of a frontier kingdom. Rulers don't explore hexes. They hire adventurers to do it for them.
2) I let my players use the Exploration Edict to have boring hexes explored for them. If something interesting is in one of their hexes, their hired explorers might not come back.
3) IMC, the unexplored hexes aren't filled with monsters waiting for the players to come kill them. They're filled with creatures and things with their own agendas or that can threaten the kingdom. Now, obviously, a carnivorous plant isn't going to do much but stand their and be carnivorous. But the Dancing Lady, Hargulka, Vordakai, Nomen Centaurs, Hannis Drelev, boggards, spirit naga, Sootscale Kobolds, and other assorted encounters are creatures, even communities, with their own agendas. Hargulka might start his own kingdom, to use an example much beloved on this messageboard.
4) Let your players play a second case of lower-powered PCs who explore, and give them adventures. My group has such a secondary group of adventurers, dubbed "the Expendables," who explore the lands around the kingdom and have adventures. So far, they have explored Fangwood Keep, faced down [http://paizo.com/products/btpy8bal?Pathfinder-Module-Masks-of-the-Living-God]Razmiran cultists[/url], and battled the ruthless Shadowscale Kobolds, among other adventures. The Kingmakers pretty much set the agenda in that portion of the game, and my players accept a little bit of railroading for the Expendables.
5) Don't be afraid to toss out some of the wilderness. I excised most of the non-plotty encounters in VV because there wasn't much point to them. Spiders? A carnivorous plant? Who cares?!
6) Give your players strategic reasons to explore and conquer. Rumors of a ruined keep, ancient, abandoned mines, and such are good reasons to go out and see what's there.
7) Remember the Stolen Lands aren't just a theme park. They're alive. If your players don't explore and claim, some one else will. Mivon might be interested in claiming that nice little river. Drelev might claim the old dwarven fort that is now home to trolls. And Maegar Varn might take over Varn and cast his eyes westward ...
