Or even just in general... If some of the zombie varieties could use the the new A* pathing, and others use some other algorithm, that would add a ton of variety I think.
The other algorithms don't even have to be anything computationally complex. The old pathing algorithm would work, or even just a straight-line-to-target path. Or different A* heuristics could be used (e.g. Manhattan vs. Euclidian) for different types.
This would probably make the game a bit more realistic, since you wouldn't just see a line of zombies following the same path to the same weak block. It would also mitigate many of the base building exploits that others have come up with.
Of course, that's assuming it's cheap (both computationally and in terms of man-hours) to swap out algorithms, which is a big assumption.
EDIT: Of course, the best thing of all would be if the algorithm could be modified in the XML. A man can dream, can't he?