If your algorithm is slow you may want to run it and then save the results. The actual game then would just use the results as the path. Dynamic path finding has quite a few hurdles to overcome and IMO does not fit with how we as humans would path find our way from point A to point B.
One thing to think about is that we cannot possibly find our way from point A to B easily without having done it before. So perhaps a bad guy should be a bumbling idiot as he runs from your player if he has never seen the rest of the world. I think games are going the wrong direction by having the AI know more than it should which usually results in wacky behavior.
You can run A* for short distances and come up with a reasonably good result. However A* is just a tool and the best pathfinding algos are probably a combination of several different algos with fallbacks in case they fail. I would recommend A* for starters and then fallback to a bump and grind (similar to what mike_g suggested).
