As Frederick Ramm put it recently, "Look at our current map at zoom level 2 and try not to run away crying." I think I'm finally making progress.
I've built some shell script hacks to work my way through a long list of z8 tiles. It is going to take weeks at my current rate, but that's OK.
I take a swath of z8 tiles, hundreds at a time, and rebuild them. Then I rebuild the z4s they inhabit, and then finally z0. This takes several days per cycle.
I also built some scripts to find and clean "unknown tile" artifacts. I'm better, or at least more comfortable, writing shell scripts than perl, so my scripts tend to be slow and kludgy, but I think it is working.
The "unknown type" tile has a certain color in the text, so I do a quick check for it at z8 using ppmhist. If I find it, then I loop through the z12 tiles inside to see if any match the unknown type tile. If I find one, I replace the image and then use the API to flag it for re-rendering. Replacing the image is a short-term fix but it is making the map at least look a little better, a little sooner. I'm checking both the "tile" layer and the "captionless" layer. If one is unknown and the other is not, I just copy one to the other. If both are unknown, I copy in the mapnik tile. In any case, the image will get replaced by a proper rendered tile soon.
I think I can look at z2 without crying so much now :-)