<p>The large network (of small world graph type) I wish to deal with is dynamic in nature, new nodes are added and subtracted frequently. Presumably using D* over A* would be a better way to detect paths in this dynamic environment?</p>

<p>How solid is D*? has it had any real world experience? like a cryptographic algorithm - is  D* hardened by lots of peer review and testing? Would you use D* for this problem?</p>

As I understand, the first time you run D* it finds the same path as A* with nearly the same runtime.  However, when a node changes it's edge value or nodes are added A* recomputes ALL of the path while D* simply recomputes the inconsistent nodes the second time around rather than the whole thing.
Anthony Stentz's D* algorithm (original whitepaper
here
) has largely been deprecated by derivatives of his work.  D* Lite and LPA* are the most commonly found and are much easier to code/implement.
As far as real world experience,  Joseph Carsten and Art Rankin from NASA's Jet Propulsion Laboratory installed a version of Field D* using elements of D* Lite on the mars rovers "Spirit" and "Opportunity" (slideshow of rovers using D*
here
).  In Feburary 2007 it was used to fully navigate the mars rover autonomously.
alt text http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg
Apparently D* is really useful in the robotics domain because the robots on-board sensors are constantly re-evaluating edge values.  That would make it pretty "battle tested" in my own opinion.
Similarly, I found another
whitepaper
that mentions the use of the D* Lite algorithm in Mobile Gaming.
I'll end this answer by stating that I've never implemented D* before, only A*.  Because of the significant increase in complexity I would say that D* (or D* Lite) should only be used in cases where there is a significant and frequent changes in the graph.  You described your situation as being similar to that so I would say definately go for D* Lite.  If NASA uses it you could safely bet it has been thoroughly investigated.