Grants Pass, OR
Well, this "Domain" is truly in a mess as you have stated. Without the ability to "see" more detail, I'm not comfortable in trying to provide much in the way of further assistance. It does appear though, that the Exchange server is still "joined" to the non-existent DC and breaking that is problematic at best.
Do you have the Domain Administrators password?
Have you checked both of the current DC's for having the DNS server roll?
That would be my first choice of where to start. Then maybe, you can start to correct the rest of the problems.