I think that yes, Skyrim should be Skyrim, but they should let you have mini-quests in which you can go to another province just for this quest and just in a certain small area of this province.
Like in Assassin's Creed Brotherhood, how you can send your assassins to quests in Lisbon or other countries, just that in Skyrim it would be you actually going to "Lisbon or other countries", every time that I was listening to rumors in Oblivion I always though to myself: "svcks I couldn't be there to see it..." or "svcks I couldn't help..." etc.