They should be trackable. They should probably be trackable from further back on their trail. What they shouldn't be is trivial to find every time you need one.
If, on average, it takes a given adventurer a day and a half or so to find a sage when they're looking for one, I wouldn't consider that excessive.
If that's becoming a serious frustration because you spend most of your time looking for them, that suggests to me that something's off about the balance of options in the game, as I don't think finding sages should be the main thing adventurers are doing most of the time.