Das Problem beim Boten ist, das er in jeder Stadt nach einem sucht und nur in den Städten, also nicht Wildnis, Herberge, Siedlung oder Dungeons. Welche Städte in welcher reihenfolge ist Gevatter Zufall. Solltest du also zwischendurch die Stadt gewechselt haben und bist in die gereist in der er gerade war kann es ewig dauern bis er dich findet. Also so lange in einer Stadt warten bis er auftaucht.
Am besten ist es immer direkt nach dem Gespräch mit dem Fuchs noch in der selben Stadt zu warten, dann müsste der Bote einen innerhalb von 8 Std. gefunden haben.
Allerdings sollte man nach einer Woche dann doch gefunden worden sein, deswegen würde ich zur Not nen früheren Save nehmen und nach dem Gespräch mit dem Fuchs ebend warten, wenn dann wieder nichts Passiert ist es wohl ein Bug. Aber das ist nun nicht wirklich hilfreich, oder?