It's not a matter of exploring. A person's mind generally can't remember the location of every NPC in the game. That's simply not practical. If the general location is not provided, it's nothing but frustration. No player should have to walk around for 1-2 hours to start a quest.
I suppose it is theoretically possible to track all the quest details. We all do it in life with appointments and such. And the game does provide the information (come back when you are level xx). But you're right, I don't want to pull out my appt. book for a game.
Instead, like a well trained rat looking for food, I make a point of visiting each quest NPC every 1-2 levels (wish there was a faster way to get to the Junction Inn), the price I pay for not remembering details. So, I propose a compromise.
* When receiving a new quest line stay with the current system. Except for a very few hidden or puzzle quests they already tell you where to go.
* Quests that call for finding have adequate clues in the description, but do not receive a map marker (there is still an item marker when close).
* When you are supposed to return to an NPC (as would have applied in this case) you receive a new quest reminding you when it is time. Essentially an 'if you have completed the last set of A. Fermii quests, add a new quest at the appropriate level to return'. The quest text could give details. I believe this may also be easier to implement then changing the functionality of the quest log.