Also check this question (and especially the answers) from the CS Theory SE:
http://cstheory.stackexchange.com/questi...ng-graphs-d-d-l

Bottom line is: There is, as usual, no silver bullet when it comes to path finding. Pick a solution that solves the problems that you have.

(Btw, if anyone wondered how StarCraft does their AI and get it performant with hundreds of moving units and changing obstacles while your A* breaks down with just a few units: They use D*)