If you think about it, there are two high-level options for pathfinding; pre-computed or real-time. The type of the game should dictate which is the best option.

For a game where the map is static and doesn't change dramatically, then pre-computed paths can give you perfect results almost instantly. I have another thread here that discusses this concept and implementation in detail. Using MX (not 2004) on my machine, I was able to generate the path denoted by the orange line here in 10 milliseconds. I promised that I would finish up the tutorial soon, sorry that it's not done but real world stuff got in the way.

If the map changes a lot, then real-time is pretty much the only way to go. Jobe Makar's new game book has a VERY fast implementation of A* in it. I don't know if it's the fastest out there in Flash, but I do know that it's probably close. It's the most flexible and robust A* implementation I've seen in Flash as it has full support for multiple terrains, is fully OO, and is easy to implement in your own code. You could probably make it a touch faster if you were to make it less generic. He uses some tricks to reduce garbage collection and object churn too.

Personally, I feel the ideal solution for pathfinding in large-map Flash games can be reached with a technique using both run-time and pre-computed paths. This huge map here shows a path that was partially generated via pre-computation (the blue line) and partially via run-time (the green lines). If you were to couple this with a LOD-style AI (Level Of Detail), you could have your characters walking around in the background without sucking all your CPU pretty easily.

For reference, I BELIEVE it's the "AI Game Wisdom" book that has an article from BioWare about how they do pathfinding for all the thousands of characters in their "Never Winter Nights" game. It's LOD based and very clever. Basically, the distance from the main character dictates the "accuracy" of the walk path. They then switch from pre-computed to real-time as needed.

Feel free to let me know if you have any questions. Thanks!