you are quite correct, I do always default to thinking of a map as an 'array of cells'. Its a simple concept for me to wrap my mind around. BUT....The issues you mention are just because you're thinking in terms of an 'array of cells'. As I suggested before, you should not think or lay out the map this way..... Another thing to consider is to go the extra mile and lay out the map(s) in terms of nodes of different sizes (ranging from entire regions of the world down to a house, for example), and to use better data structures (priority queues and spatial hashes, say). That way, you can have a multi-tiered path finder that can query the entire world if you want. And you don't waste any memory (if that is your main concern) in cells that won't get visited, ever.
I need to think about what you are suggesting regarding the map being a graph of different sized, interconnected nodes. What appeals to me about that concept is that it is very memory efficient, and, as you point out, the pathfinding would gain great speed benefits compared to standard uniform graph.... very interesting, now to see if I can conceptualize it enough to understand how it would basically work, coding wise.... this will take a few days... lol
The Dungeon Siege pdf was interesting, alot of terms I don't understand, but could sometimes figure out.