After weeks of trying to come up with a fast and accurate pathfinding solution for a project i stumbled upon this article by Gustavo Franco:
http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527
Even tough it didn't run right away, because the server blocks certain unsecure methods, i was able to modify it to be compatible with PlayerIO. Feeling this could be as helpful to some as it was to me, i set up a simple project that implements server side pathfinding. For the sake of simplesness i created a 10x10 grid with few obstacles, but i have successfully done some tests with a 1024x1024 grid and lots of obstacles without the server complaining about taking too long. In fact even on such large grids the path is usually found whitin miliseconds.
Here's the demo:
http://ageofmerlin.com/As3PathFinding.swf
And here is the c# server project:
http://ageofmerlin.com/pf/CSPathFinding.zip
And the Flash Builder 4 project (i used none of the Flex framework components so you can still convert it to Flash if you prefer):
http://ageofmerlin.com/pf/As3PathFinding.zip
None of the code is to be taken as good coding practises, i know even for a small project there's lots of optimization that could be made. The Pathfinding algorithm created is very very flexible and accepts lots of parameters, more than enough to do any kind of pathfinding. Consult Gustavo Franco article i posted earlier and download his demo project where you can test all the kinds of pathfinding you can do with it.