You are right AD issues are almost always DNS issues. I think the issue is with having the firewall set as a secondary DNS on your DC IP settings. Remove that from the NIC configuration and instead add the firewall as a forwarder in the DNS configuration.
This will force all DNS resolution to start with the Windows DNS and addresses it doesn't know about will be queried through the forwarder.
Once you reset the DNS settings, run ipconfig /registerdns on the DC to fix the AD registrations in DNS.
Also, all your Windows servers and clients should point only to this DNS. If you need an alternate DNS, install DNS on another server (it does not need to be a DC to run DNS).
Edit: Because of your edits and followup comments, I really believe that their is either a script in the local startup folder doing this on each machine, or you're just missing where one is being called in rsop.
SYSVOL can be empty and startup scripts can still be called from other shares as long as the permissions are correct. There's no requirement that a statup/logon script must exist in SYSVOL.
All the clients have been hard coded to use the domain controller as their DNS
You shouldn't do this. I'll explain why later.
Since these are new machines, and I never changed their DNS settings, I'm guessing there must be a GPO that's causing them to use the domain controller as their DNS
Probably not. The GPO to force DNS settings only works on XP or earlier. If these are new machines, they're probably not XP, meaning that if there actually was a GPO enforcing this, it wouldn't apply to anything Vista or later.
The only thing that I can think of, as pointed out in the comments, is a logon script, or a conditional forwarder from the other domain that's in this picture (as described in your previous question).
Since we don't have any GPO other than the default one yet, it's got to be the default GPO, however, I have looked through all the GPO settings and none of them refer to anything related to DNS.
If you really want to dig into what GPO settings are applying, look through the output of gpresult /H c:\gpo.html and rsop.msc. These are the two primary tools for troubleshooting GPO issues.
So I'm wondering if there's anything else that might be causing this.
Yes, most likely you've configured the DNS Server DHCP option on your DHCP server. This is how you actually want to distribute your DNS Server search list. By hardcoding it, you make it a real PITA to change down the road. Microsoft agrees with this, as evidenced in their choice to deprecate the GPO that sets the DNS server list for clients.
You should make sure that your DHCP server is handing out the right DNS servers to clients and then stop statically configuring it. There's no reason to.
Best Answer
Static IP addresses are not automatically registered with DNS controllers the way that DHCP granted ones are. I am sure that there is a way to force the registration although I don't know what it is. Alternatively, if you own the DHCP server you could do the static assignments with DHCP reservations instead of static assignments on the server which would cause them to register the IPs with the DNS server when they obtain the lease. Hope that helps.