I've always enjoyed the idea of an RPG with a similar system to what you describe. The levels of complexity that it can add are boundless, which is probably why serious implementation of the concept has been surprisingly lackluster. For example, why stop at NPCs who are just wandering around waiting for you to find them? What about NPCs who can kill monsters, complete quests, acquire vital game items, kill each other or drive major story events?
As long as the game isn't trying to be real-time, I don't think moving the NPCs around would be a significant problem. Give each NPC a quest or objective, and, say a food/provision supply so they need to restock in a town every so often. Each turn the player takes, the NPCs also move about the world in the direction of their current objective. If the player and NPC happen to meet on the same square, or in the same town/dungeon level, then there is an encounter. Maybe plesant conversation, maybe combat. Maybe you hide in the bushes to avoid them. Tracking might be a harder issue, since it would require a prior knowledge of where the NPC had been previously. Maybe only the last few (2 or 3 squares on an ADOM worldmap, say) that the NPC has visited are trackable would be sufficient? After that tracks are too worn to be seen, say. Maybe you could have spells that detect the instantaneous locations of NPCs on the board, or seers that you could pay to tell you where someone is/where they're going so you can try to meet them there.
Hoping to win with every class, doomed. Archer, Barbarian, Bard, Beastfighter, Druid, Elementalist, Farmer, Fighter, Monk, and ULE Priest down.