Later on in the campaign Hexploration basically became a background feature, we still did it, but didn't focus on it as much - certainly random encounters were more focused and less 'random' We found that by book 5 there was very little.
What I did do was give the players the Kingmaker Maps later on. They came across them in various places and, though they didn't know the specifics they knew generally where to go.
They airwalked to Whiterose Abbey for example, and and pretty much took magical means to get everywhere. The wizard had Greater teleport so it was never really an issue. In fact it made the campaign feel suitably high-magic as they swiftly moved about it. Of course their armies couldn't but they could take a more strategic view.
It all worked out.
They never hexplored the Forest of Thousand Voice - wasn't ever a problem.