DHCP IP lease renewal ok, but a new PC can not obtain an IP ("An error occurred while renewing interface Local Area Connection : unable to cotact your DHCP server. Request has timed out.")

Dear reader,

not sure this is the right forum for my question, so I in total have posted it in the forums:
microsoft.public.win2000.dns
microsoft.public.win2000.networking
microsoft.public.windows.server.dns
microsoft.public.windows.server.networking
www.experts-exchange.com/Operating_Systems/Windows_Server_2003

Any solution or directions to what to do much appreciated.

The environment:
In our (single) domain we have +50 XP PCs and 4 Windows Server 2003 DCs (3 in-house being "maria", "tina" and "robert" and 1 being "oscar" in remote location).
One DC (robert) run the DHCP Server service (and DHCP Client service for registering and updateing IP addresses and DNS records for this computer).
All 4 DCs run DNS (two zones).

The following server roles/functions apply:
erik: dhcp (running but not defined nor used by any PC). 192.168.65.80
maria: dns, secondary wins. 192.168.65.76
oscar: dns (though no PC currently point to this). 192.168.65.25
robert: dhcp, dns, primary wins. 192.168.65.3
tina: dhcp (running but not defined nor used by any PC), dns, secondary wins. 192.168.65.4

No changes implemented(! as certain as I can be) in regards of any of these servers within the last week.

a. The problem:
a.1.  XP PCs runs fine and can renew (re-obtain) IP leases from our DHCP server. However a PC which has not got an IP fails to get such from the DHCP server. The PC is for sure "on the network" (e.g. manually assigning an IP and it runs "fine").
a.2. "ipconfig -renew" show a new Lease was obtained (updated time also for when the lease expires).
a.3. "ipconfig -release" followed by "ipconfig -renew" result in the error message "An error occurred while renewing interface Local Area Connection : unable to cotact your DHCP server. Request has timed out.".
a.4. Restart of a PC and it get's (unknown how/from where) IP 169.254.5.70 (or any other within the subnet range 169.254.x.x.) , netmask 255.255.0.0 and no default gateway.
a.5. Same as a.4. when an IP has expired (e.g. a PC was powered off last night and this morning had the problem).

b. Other problems/symptoms:

c. On robert Windows Server 2003 (Version 5.2 (Build 3790.srv03_rtm.030324-2048)" - role DC, dhcp, dns, primary wins:
c.1. In dhcp managment console see erik as running (no DHCP is defined on this though), "Cannot find the DHCP Server" on tina nor oscar. robert self has DHCP defined and I can see all of this.
c.2. In dns management console see oscar and maria fine, but get error "Unable to connect to the computer "tina". The error was: The network path was not found." and "Cannot Contact the DNS Server" from tina.
c.3. DHCP Server plus Client and DNS Server plus Client services running.
c.4. Ping erik, maria and oscar but not tina ("Request timed out").
c.5 Map a network drive to erik, maria and oscar but not tina (get error: "The drive could not be mapped because no network was found")
c.6 +50 available IP's in DHCP scope.

Restarting robert result in the following error entry in the SystemLog:
Event Type:      Error
Event Source:      NetBT
Event Category:      None
Event ID:      4321
Date:            02/06/2005
Time:            12:03:58
User:            N/A
Computer:      ROBERT
Description:
The name "OURDOMAIN       :1d" could not be registered on the Interface with IP address 192.168.65.3. The machine with the IP address 192.168.65.76 did not allow the name to be claimed by this machine.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.
Data:
0000: 00 00 00 00 04 00 56 00   ......V.
0008: 00 00 00 00 e1 10 00 c0   ....á..À
0010: 01 01 00 00 01 00 00 c0   .......À
0018: 00 00 00 00 00 00 00 00   ........
0020: 00 00 00 00 00 00 00 00   ........

Followed by:
Event Type:      Error
Event Source:      W32Time
Event Category:      None
Event ID:      29
Date:            02/06/2005
Time:            12:06:42
User:            N/A
Computer:      ROBERT
Description:
The time provider NtpClient is configured to acquire time from one or more time sources, however none of the sources are currently accessible.  No attempt to contact a source will be made for 15 minutes. NtpClient has no source of accurate time.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.


And later:
Event Type:      Error
Event Source:      DhcpServer
Event Category:      None
Event ID:      1059
Date:            02/06/2005
Time:            12:07:26
User:            N/A
Computer:      ROBERT
Description:
The DHCP service failed to see a directory server for authorization.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.
Data:
0000: 3a 20 00 00               : ..    

However, this is followed immeditately by the entry:
Event Type:      Information
Event Source:      DhcpServer
Event Category:      None
Event ID:      1044
Date:            02/06/2005
Time:            12:07:26
User:            N/A
Computer:      ROBERT
Description:
The DHCP/BINL service on the local machine, belonging to the Windows Administrative domain ourdomain.local, has determined that it is authorized to start. It is servicing clients now.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.
Data:
0000: 00 00 00 00               ....    

Some minutes later another error entry is seen:
Event Type:      Error
Event Source:      NETLOGON
Event Category:      None
Event ID:      5719
Date:            02/06/2005
Time:            12:18:54
User:            N/A
Computer:      ROBERT
Description:
This computer was not able to set up a secure session with a domain controller in domain OURDOMAIN due to the following:
There are currently no logon servers available to service the logon request.  
This may lead to authentication problems. Make sure that this computer is connected to the network. If the problem persists, please contact your domain administrator.  

ADDITIONAL INFO
If this computer is a domain controller for the specified domain, it sets up the secure session to the primary domain controller emulator in the specified domain. Otherwise, this computer sets up the secure session to any domain controller in the specified domain.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.
Data:
0000: 5e 00 00 c0               ^..À    

d. On tina Windows Server 2003 (Version 5.2 (Build 3790.srv03_rtm.030324-2048)" - role PDC, dns, secondary wins:
d.1. In dhcp managment console see erik as running (no DHCP is defined on this though), "Cannot find the DHCP Server" on robert nor oscar. tina self have no DHCP defined.
d.2. In dns management console see oscar and maria fine, but get error "Unable to connect to the computer "robert". The error was: The network path was not found." and "Cannot Contact the DNS Server" from robert.
d.3. DHCP Server plus Client and DNS Server plus Client services running.
d.4. Ping erik, maria and oscar, but not robert ("Request timed out").
d.5 Map a network drive to erik, maria and oscar but not robert (get error: "The drive could not be mapped because no network was found")

e. On erik Windows Server 2003 (Version 5.2 (Build 3790.srv03_rtm.030324-2048)" - role member server:
e.1. In dhcp managment console see erik and tina as running (no DHCP is defined on these though), "Cannot find the DHCP Server" on oscar, and robert can be seen having DHCP defined and I can see all of this.
e.2. In dns management console see all: oscar, maria, robert and tina. No dns defined for erik self.
e.3. DHCP Server plus Client and DNS Server plus Client services running.
e.4. Ping all: maria, oscar, robert and tina.
e.5 Map a network drive to all: maria, oscar, robert and tina

f. On maria Windows Server 2003 (Version 5.2 (Build 3790.srv03_gdr.040410-1234)" - role DC, dns, secondary wins:
f.1. dhcp managment not installed.
f.2. In dns management console see all: erik, maria (self) oscar, robert and tina. No dns defined for erik.
f.3. DHCP Client and DNS Server plus Client services running.
f.4. Ping all: maria, oscar, robert and tina.
f.5 Map a network drive to all: erik, oscar, robert and tina.

g. On oscar Windows Server 2003 (Version 5.2 (Build 3790.srv03_gdr.040410-1234)" - role DC:
g.1. dhcp managment not installed.
g.2. In dns management console see all: erik, maria, oscar, robert and tina. No dns defined for erik.
g.3. DHCP Client and DNS Server plus Client services running.
g.4. Ping all: maria, oscar, robert and tina.
g.5 Map a network drive to all: erik, maria, robert and tina.

I am out of ideas and will be happy about your feedback.

Kind regards,
Soren Mikkelsen
Switzerland