Rebuild em. Sounds like the time and effort you have spent troubleshooting this one at this point could now have easily rebuilt Win2K Adv. server and reinstalled metaframe. That's usually my policy after 6-8 straight hours of troubleshooting, rebuild it. As a DC's they should not have much in the way of data stored on it (RIGHT?) This time, don't make them DC's if you can avoid it.
Look at the bright side... You will have nice clean (and working) boxes again. I personally don't like the upgrade path. Clean build is the way to go IMHO. Remember the Win95 to 98 debacle? Yuck. (For that mtter remember DOS 5- DOS 6!!?! OUCH!)
If you can rebuild one of em, make a ghost image if the hardware is identical. You can have them all rebuilt in just a few hours if you use multicasting.
As for letting the servers use DNS to resolve a license server, I personally prefer to know that they are getting them from one single place...Just my prefference so I can watch the licenses on the server. Her's a possibility...Perhaps the license server these servers are finding is out of licenses? This can happen if it's not purged regularly. Every 4 months or so, my 3000 users eat up 10,000+ TS licence servers licences, if not periodically cleaned up.
Dave