Well, I can see a couple solutions to this problem. First is that, if it's really that common for the heroes to spend so much time traveling, maybe it's similarly more common for their allies to travel as well? So Contacts as presented in the rules could just be a lot more available, because they are already accustomed to traveling and because they are more likely to be nearby when the characters call on them. You might allow that if the PC is within the Contact's home region (nation, continent, or whatever scale you're operating at) then they can be easily summoned as normal, and when outside that region, some additional measures need to be taken, such as sending a message via courier. And then the Contact may or may not be willing to make the trip, at your discretion.
The other option is similar to what you suggested. Rather than a contact being a single character, it could represent a network of characters. So rather than the PC gaining the favor and service of Friar Tuck, the PC instead gains the favor of an order or Friars. When the PC wants to call on this "contact", it's simply a matter of deciding whether there is a member of this order in the area and if there is, finding him, which might involve some skill check, or not.
With either option the Explorer's core ability works pretty much unchanged. Spending an action and waiting a few hours guarantees that his contact will be available. But, it also makes everyone else's contacts more available, without necessarily trampling on the Explorer.