AD, DNS, WINS, Certificates and Missing Machines

Strange AD connectivity problems between servers? Inconsistent results? I created a really strange scenario that caused all sorts of problems, and figured out how to fix it: 

• Problems with getting machines to form proper domain trusts and relationships, can't find resources and RPC server errors

The issue occurred when all of these conditions occurred:

• Machine also had external DNS resolvers
• Machine used those resolvers to try to resolve internal domain machine IPs
• machines had different DHCP IPs and got put in old WINS before joining new domain
• Old WINS was on same server as the "public" version of our domain DNS name (no corp.local here)
• machines were resolving old DHCP/WINS addresses for other machines instead of new private domain ones
• Broke basic DNS lookups for other machines, found with a simple ping test