Computer hanging at applying computer settings

I could really use some help here. My situation is this.

I have around 200 machines on a windows domain. The Domain controllers are running windows server 2003 and our exchange server is running exchange 2000.

Recently some of our Windows XP SP3 machines have started hanging at the applying computer settings in the boot up process. I can fix it by pulling out the network cable.

Upon checking the event logs in the client PCs I see that they have an error with net logon saying the DC cannot be contacted.

I have tried everything I could think of. So far I have tried the following:

Checking the DNS configuration and manually entering the IP Address of the DNS server on the client PCs. Still didn't work.

Using a packet sniffer to make sure the client PCs were talking to the DCs and they were.

System restores. Still didn't work.

Disabling the firewall on the client PCs. Still didn't work.

Moving the PC into a container on the domain which has no group policy settings. Still didn't work.

Checking the windows update servers for common failed updates on the client machines. There were no common failed updates.

Deleted all the user accounts on the client machine apart from the admin account. Then creating a new domain user account on the client. Still didn't work.

Removed the antivirus software on the client PCs. Still didn't work.

Rebooted the DCs. Still didn't work.

Reset the computer account on the DC. This caused some strange things to happen to the client PCs. After resetting the account I was able to get past applying computer settings. However at the login box when I try to log onto the machine using a domain account I get told "the system cannot log you in now because the domain is not available". To fix this I log on as a local admin disconnect from the domain, reboot and then log in as the local admin and reconnect to the domain. After this the PC gets past applying computer settings but after you log in it then hangs at loading personal settings. To fix this I have to remove the network cable.

The only tried and tested way I know to fix it is to reformat the machine. However this isn't really a very good fix as it would take too long to go round all the machines and reformat them.

I think that the problem may be something to do with the DCs. Could this be related to a replication issue between the DCs?

I am at my wits end any help at all would be really appreciated.