Both major game development sites have had recent features on path-planning techniques. The first is an image of the day over on Flipcode, which shows a grid based search tool used in the author's landscape engine.

The second is an article on GameDev called Knowing the Path. The author apparently uses a familiar matrix to store the paths step by step. Despite being reasonably suited to dynamic conditions, there are many problems with this approach -- including scalability since the matrix approach can get huge! Nothing amazing, but might be worth a quick read...

Sorry for the lack of updates, I was out of town for the weekend!