Active Directory Group Policy Issue after Domain Rename

In my opionion 32 - 40 billable hours to perform the testing necessary for a domain rename in such a small infrastructure is insanely high.

The configuration you describe could be tested in an afternoon with a couple of physical "scratch" client computers, a virtual domain controller, and a virtual member server on an isolated LAN.

I'd start by obtaining a test domain controller by installing a VM connected to the LAN, joining it to the domain, and promoting it to a domain controller. I'd install a DNS server, mark it as a Global Catalog server, and set it to refer to itself for DNS. Once all AD replication completed I'd take a snapshot of the VM, and then demote it back to being a member server before removing it from the domain. This leaves the production AD domain in a state consistent with how it started.

I'd detach the VM host from the LAN (or otherwise isolate it), reboot the domain controller VM from the snapshot taken when it was still a DC and seize the FSMO roles to it. This gives you a DC "under glass" to work from. I'd join a couple of "scratch" client computers to the domain hosted by the DC in the isolated network, and bring up a test file server VM as a member server. Once I verified that the "domain under glass" functioned properly I'd proceed with taking snapshots (to give me a fall-back position to re-start testing) and start the domain rename resting.

Domain rename without an Exchange 2003 infrastructure to worry about isn't something you should be too scared of. It's reasonably well documented (others provide links in their answers that are reasonable) and is "supported" by Microsoft. As you've already noted, doing it before you deploy Exchange is important because this is your last chance to rename the domain.

The Problem happened again on another DC. It turns out that a few files were in the C:\Windows\Sysvol\domain\scripts folder - some exe files running. NTFRs.exe couldn't complete its task.

ntrfsutl was useful to debug this problem. http://support.microsoft.com/kb/822300/en-us is a certainly helpful. I used ntrfsutl inlog to see the state of files being transfered. For my case, the scripts folder was in state IBCO_INSTALL_REN_RETRY all the time. I then located all the files which held locks in the script directory (and its sub directories). Those were a few programs which were also running on client computers (but opened over the NETLOGON share).

You can use handles.exe from SysInternal Tools to identify open file handles. In my case some files were opened by the "System" process. Those were actually opened over the network share by client computers. I closed their handle via compmgmt.msc.

After all opened handles were closed, the replication finally succeeded.