If I were doing this, I'd focus more on the NPCs than the pathfinding. I'd come up with "motives" for an NPC and determine, based on whatever, "where does this NPC want to go right now?" and I'd put most of my effort into making these decisions rich and intuitive rather than spending that time on pathfinding.
Once I have the destination in mind, I'd have the game take note of which map they will be on as they traverse from their start point to their destination map, so that the player could "run into them" on the way.
But as far as the pathfinding, I'd use a real basic system like I did for automated player movement in timeblazer: set movement loops to keep moving (for example) up or down (based on their start point) until the character reaches y == 8, then right until they reach x == 30 (the map's exit). Where there are maps with concave features (such as a courtyard with 3 walls) this basic form won't work as well but you can get around that by using different loops (such as one where they move up until y == 12, then right until x == 16, then up again until y == 8, then right again until x == 30) based on their initial start point on the map.
In a large world where NPCs can literally go from anywhere to anywhere else, this approach would be inefficient for the designer's time (though still very efficient from a computing resource standpoint), and you might want to turn to developing true search algorithms for pathfinding like suggested.
But you'd still need to do all of the setup necessary to determine where each NPC wants to go in the first place.
Also, I'm pretty sure there are some scripts out there that create "smart" routes for events/NPCs/the player to move from Point A to Point B on a single map. So as long as you're tracking behind the scenes which maps the NPC should be moving toward, you can probably just plug in one of these scripts, set the appropriate map exit as the destination, and continue from there.
