On a somewhat related topic I got around to updating my pathfinder library implementing a few suggestions made by Iain. This version should help significantly speed up cases in which you don't want any long paths generated in favor of speed.
The maxnodedepth lets you specify the max length of the path and if you set a minnodedist proc you'll be able to eliminate testing of a huge number of nodes.
However one thing to be aware of is that even though you may get a path it may not be the "shortest". For instance if you let your characters wade through lava and you're on one side of a lava river, the destination is on the other and a bridge is a good distance away. If you set the maxnodedepth to a small value your path will go straight through the river ignoring the bridge in the distance if it takes too many nodes to use even though according to the dist proc passed in it may be shorter to use the bridge due to the high weights of the lava tiles.