What you need is called pathfinding. While you can build the code yourself, you might find luck in some of the already existing code on the net. There are a few A* pathfinding algos out there. I did not use them, so I don't know if they are any good (should be).
I haven't studied the theory, but I've made a pathfinder or two for my own use in the past (packman non-tile based game, for example). It's either a recursive function-functions or while-for loops arranged to behave like recursive code (so that they don't overflow the stack).
You can get away in flash with recursive functions, you won't have to many enemies running around. That is, if you're not using a tile based map. If you are (you should with your experience), A* classes on the net should do the heavy lifting for you quite well. There is also the high level tile - low level non tile hybrid but that's even more advanced and you won't be able to run such a game in flash (flash is really slow, even as3).
If you run into performance trouble, use tricks like you described earlier, don't pathfind for somebody who is not in range etc...
Edit: yes, if you have walls, basically, you need to precompute a path (make path points). Just google "pathfinding wiki" to get some theory first, read 10-20 pages of wikipedia and you'll be set to go. Find some code examples (search again) and test in a 5x5 tile based map (matrix, two dimensional array...)