Windows – Directory Service is unable to allocate a relative identifier

At work, we currently have one domain controller, POLLY. This DC is the RID master. However, there used to be two other DCs, PAULA and PETTY. These are both offline (and long gone), yet they appear in POLLYs configuration. Strangely, POLLY has the same IP as PETTY.

When I try to add a new user with Active Directory Users and Computers, I keep getting the following error message:

Windows cannot create the object because the Directory Service was unable to allocate a relative identifier.

This is strange, since POLLY (our only DC) is the RID master.

Here's the output of dcdiag:

Domain Controller Diagnosis

Performing initial setup:
Done gathering initial info.

Doing initial required tests

Testing server: Standardname-des-ersten-Standorts\POLLY
Starting test: Connectivity
……………………. POLLY passed test Connectivity

Doing primary tests

Testing server: Standardname-des-ersten-Standorts\POLLY
Starting test: Replications
REPLICATION-RECEIVED LATENCY WARNING
POLLY: Current time is 2012-01-11 09:18:28.
DC=ForestDnsZones,DC=europa-institut,DC=com
Last replication recieved from PETTY at 2004-08-12 17:48:21.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
DC=DomainDnsZones,DC=europa-institut,DC=com
Last replication recieved from PETTY at 2004-08-13 10:50:52.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
CN=Schema,CN=Configuration,DC=europa-institut,DC=com
Last replication recieved from PETTY at 2004-08-12 17:48:20.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
Last replication recieved from PAULA at 2004-08-25 01:05:28.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
CN=Configuration,DC=europa-institut,DC=com
Last replication recieved from PETTY at 2004-08-13 10:54:37.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
Last replication recieved from PAULA at 2004-08-25 01:05:19.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
DC=europa-institut,DC=com
Last replication recieved from PETTY at 2004-08-13 11:04:57.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
Last replication recieved from PAULA at 2004-08-25 01:09:36.
WARNING: This latency is over the Tombstone Lifetime of 60 days!
……………………. POLLY passed test Replications
Starting test: NCSecDesc
……………………. POLLY passed test NCSecDesc
Starting test: NetLogons
……………………. POLLY passed test NetLogons
Starting test: Advertising
……………………. POLLY passed test Advertising
Starting test: KnowsOfRoleHolders
……………………. POLLY passed test KnowsOfRoleHolders
Starting test: RidManager
……………………. POLLY passed test RidManager
Starting test: MachineAccount
……………………. POLLY passed test MachineAccount
Starting test: Services
……………………. POLLY passed test Services
Starting test: ObjectsReplicated
……………………. POLLY passed test ObjectsReplicated
Starting test: frssysvol
……………………. POLLY passed test frssysvol
Starting test: frsevent
There are warning or error events within the last 24 hours after the

SYSVOL has been shared. Failing SYSVOL replication problems may cause
Group Policy problems.
……………………. POLLY failed test frsevent
Starting test: kccevent
……………………. POLLY passed test kccevent
Starting test: systemlog
An Error Event occured. EventID: 0x40000004
Time Generated: 01/11/2012 08:47:35
(Event String could not be retrieved)
An Error Event occured. EventID: 0x40000004
Time Generated: 01/11/2012 09:05:49
(Event String could not be retrieved)
……………………. POLLY failed test systemlog
Starting test: VerifyReferences
……………………. POLLY passed test VerifyReferences

Running partition tests on : ForestDnsZones
Starting test: CrossRefValidation
……………………. ForestDnsZones passed test CrossRefValidation
Starting test: CheckSDRefDom
……………………. ForestDnsZones passed test CheckSDRefDom

Running partition tests on : DomainDnsZones
Starting test: CrossRefValidation
……………………. DomainDnsZones passed test CrossRefValidation
Starting test: CheckSDRefDom
……………………. DomainDnsZones passed test CheckSDRefDom

Running partition tests on : Schema
Starting test: CrossRefValidation
……………………. Schema passed test CrossRefValidation
Starting test: CheckSDRefDom
……………………. Schema passed test CheckSDRefDom

Running partition tests on : Configuration
Starting test: CrossRefValidation
……………………. Configuration passed test CrossRefValidation
Starting test: CheckSDRefDom
……………………. Configuration passed test CheckSDRefDom

Running partition tests on : europa-institut
Starting test: CrossRefValidation
……………………. europa-institut passed test CrossRefValidation
Starting test: CheckSDRefDom
……………………. europa-institut passed test CheckSDRefDom

Running enterprise tests on : europa-institut.com
Starting test: Intersite
……………………. europa-institut.com passed test Intersite
Starting test: FsmoCheck
……………………. europa-institut.com passed test FsmoCheck

And here's the output of repadmin /showrepl:

repadmin running command /showrepl against server localhost

Standardname-des-ersten-Standorts\POLLY

DC Options: IS_GC

Site Options: (none)

DC object GUID: 3c57a0b6-7047-4b42-a3d1-e5eed7513cbe

DC invocationID: 5194142b-3179-4cff-b17e-77af398b8007

What do I have to do in order to be able to add new users?