Josh made me aware of the problem. Jeremy found that the problem is due to the RID Operations Master reaching the end of its allocation pool. We tried deleting over 100 accounts. This did not fix the problem.
We found Microsoft Knowledge Base Article 305475 (text enclosed here), which describes the attributes in AD that control RID operations:
——————————————————————————
Description of RID Attributes in Active Directory
The information in this article applies to:
Microsoft Windows 2000 Server
Microsoft Windows 2000 Advanced Server
Microsoft Windows 2000 Datacenter Server
This article was previously published under Q305475
SUMMARY
This article describes RID-related attributes in Active Directory.
Users, computers, and groups (collectively known as “security principals”) that are stored in Active Directory are assigned Security Identifiers (SIDS), which are unique alphanumeric numeric strings that map to a single object in the domain. SIDS consist of a domain-wide SID concatenated with a monotonically-increasing relative identifier (RID) that is allocated by each Windows 2000 domain controller in the domain. Each Windows 2000 domain controller is assigned a pool of RIDs by the RID flexible single-master operations (FSMO) owner in each Active Directory domain. The RID FSMO is responsible for issuing a unique RID pool to each domain controller in its domain.
MORE INFORMATION
RID Attributes in Active Directory
FsmoRoleOwner
DN path: CN=RID Manager$,CN=System,DC=domain,DC=com
Points to Domain Name path of the current RID masters NTDS Settings object according to domain controller that is being queried.
RidAvailablePool
DN path: CN=RID Manager$,CN=System,DC=domain,DC=com
Global RID space for an entire domain is defined in Ridmgr.h. as a large integer with upper and lower parts. The upper part defines the number of security principals that can be allocated per domain (0x3FFFFFFF or just over 1 billion). The lower part is the number of RIDs that have been allocated in the domain. To view both parts, use the Large Integer Converter command in the Utilities menu in Ldp.exe.
Sample Value: 4611686014132422708 (Insert in Large Integer Calculator in the Utilities menu of Ldp.exe)
Low Part: 2100 (Beginning of next RID pool to be allocated)
High Part: 1073741823 (Total number of RIDS that can be created in a domain)
RidAllocationPool
DN Path: CN=Rid Set,Cn=computername,ou=domain controllers,DC=domain,DC=COM
Each domain controller has two pools: the one that they are currently acting on, and the pool that they will use next. It is the next pool, which is allocated by the RID FSMO, that will be used for creation of security principals in the domain when the current pool is exhausted. Use the Large Integer Converter command in the Utilities menu in Ldp.exe to view both pools.
Sample Value: 685485370535295 (Insert in Large Integer Calculator in Utilities menu of Ldp.exe)
Low Part: 159103 (Beginning RID in the next RID pool)
High Part: 159602 (Ending RID in the next RID pool)
RidNextRid
DN Path: CN=Rid Set,Cn=computername,ou=domain controllers,DC=domain,DC=COM
The RID that is assigned to next security principal that is created on the local domain controller. RidNextRid is a non-replicated value in Active Directory.
Sample Value: 159345 (RID assigned to next security principal from RidPreviousAllocationPool)
RidPreviousAllocationPool
DN Path: CN=Rid Set,Cn=computername,ou=domain controllers,DC=domain,DC=COM
The pool from which RIDs are currently taken. The value for RidNextRid is implicitly a member of this pool. Use the Large Integer Converter command in the Utilities menu in Ldp.exe to view the beginning and ending RIDS in the current pool. RidPreviousAllocationPools is a non-replicated value in Active Directory.
Sample Value: 687632854183795 (Insert in Large Integer Converter command in the Utilities menu of Ldp.exe)
Low Part: 159,603 (Beginning RID in next RID pool)
High Part: 160,102 (Ending RID in next RID pool)
RidUsedPool
DN Path: CN=Rid Set,Cn=computername,ou=domain controllers,DC=domain,DC=COM
Unused attribute
NextRid
DN Path: DC=domain,DC=COM
Unused attribute
———————————————————————-
Indeed, the RIDNextRID attribute was 14439, the top of the current allocation pool.