This would likely be done with a graph. There are two ways to generate this graph: 1) Manually set connections between nodes, 2) Automatically set connections between nodes (based on LOS, perhaps)
Either way, you will end up with a graph with similar properties, each node having these attributes:
- links to adjacent nodes
distance to adjacent nodes
some sort of direction vector to adjacent nodes
node type
arbitrary data
CPU usage: You would not check nodes as often as you are thinking. It would be possible to store in the Mob class (for instance) the node that a player or mob is at/connected to. So, just find a path from Mob A's node to Mob B's node, probably using the infamous travelling salesman algorithm. You could also likely cache results from past checks for even more speed. In addition, a mob may only need to do a check when either its or its target's "connected to" node changes.
When to use adjacent nodes, and when to use target node: Nodes may have different types. Some nodes may be flagged as "sticky" -- you may only path to adjacent nodes when coming from this node. A node may be flagged as "free" -- go destination node if it is visible. Of course, then there is the problem of having multiple types in one area. This may be solved with using "free areas" or "sticky areas" in conjunction with nodes.
There are still plenty of problems with this system, I imagine, but maybe that gives you something more to go on.