The symptom is a classic indicator of lingering objects. If Strict Replication is enabled on a domain controller, and it detects a lingering object from a replication neighbor, it block inbound changes from that neighbor until the offending object is removed.
Strict Replication is set by default in new Windows Server 2003 SP1 domains and later.
When a lingering object is detected, an event id 1988 or 1388 is recorded in the Directory Service event log. If the domain/forest is small (at most a few domain controllers and less than 50,000 objects), you may use repadmin to remove lingering objects. Using repadmin for this purpose is not feasible on large AD implementations.
The following command will compare the specified partition on all domain controllers when * is substituted for ServerName, and log any offending lingering objects for removal:
repadmin /removelingeringobjects <ServerName> <ServerGUID> <DirectoryPartition> /advisory_mode
If you are satisfied with the report, run the command without the advisory_mode switch to perform the action.
Troubleshooting Active Directory Replication Problems
Event ID 1388 or 1988: A lingering object is detected
Use Repadmin to remove lingering objects
A similar tool is GCChk from JoeWare, although I haven't used it: