That's part of the problem, and why I'd say it's important for whatever algorithm is chosen to have two characteristics: that segmentation works locally (i.e., I just mined a tile, I don't have to recalculate all the pathing for the whole damn world), and that different areas can be re-zoned (divided or merged). If those two criteria are met, it shouldn't be a problem to deal with terrain modifications.
Incidentally, that's part of my criticism to Sunken's TCZ (an idea which I otherwise like very much). I don't think you can realistically have TCZs (much) bigger than whatever size you're using for the local checking, since it makes it easier for the silly-move requirement to be violated (a little bigger might be possible, but I don't think you could, say, have a TCZ the size of a 2x2 z-level if you're doing 24x24 local checks, even if there is some overlap between the checks - overlapping would cost CPU time, but it would result in more robust segmentation, I'd expect).
Still, and like Sunken says, I don't see why we couldn't limit these TCZs to a size that's manageable locally (say, 12x12 or 24x24), and then use a hierarchical pathing algorithm like the one in the paper Dae linked us to (awesome paper, btw - I looked for a few others in the same vein in the IEEE paper database, and found a couple I want to read, but I didn't find any quite as impressive).