Uh, actually, there was a bug in the code. Sorry for that. The message was misleading so far, it is correct now.
Also please note that sages and wizards often travel a lot slower than nobles, not having horses and stopping at small villages along the way to chat with the peasants, or to meditate in a caves. It can take several days for them to arrive at their next destination. As long as you get that "passed through recently" message, they are at most one region away.
