I too have had similar issues with MSW2KS (2000 Server). For me, it began after, I added the latest MS Service Pack (4 I believe.) Additionally, I got the same problem with my MSW2KP (2000 Pro desktop).

Similar to you, I reinstalled from scratch my MSW2KS and on my MSW2KP. It was happy days again until- I ADDED Microsoft Service Pack Updates! Then, it took 5 to 15 minutes to complete a boot-up prior to my login screen on either the Server or Pro.

I am 'guess-timating' the security part of these service packs are performing intensive TCP/IP Port checks. My personal firewall (I use Outpost v2.5 by Agnitum) is going 'buck wild' with port scan activity when I boot up now. The history data is in my Outpost logs. A tremendous amount of various Window System application accessing 'out' to the localhost (my server 'loopback' as a remote PC) and 'in' from the localhost as well as IP address duplication of the same activity as localhost. (Instead of as Remote or Local Host, it uses Internet Protocol e.g., etc.). It is VERY REASSURING that no external IP addressing or Hostnames are showing up in my Outpost Firewall logs during this boot-up. If so, then, I DO HAVE A MAJOR PROBLEM! The fact that only my PC's are having application activity to itself, gives a high % of probability these are legitimate Microsoft System activity.

Because malicious Worms from Advertising Hackers, Computer Crackers, Mischievous Programmers, Industrial Espionage Hackers, and Terrorists, are so powerful, this problem may become a necessary evil for the near future. Consider, the more programs on your server that make use of IP ports (especially if initialize at boot-up), the more work an anti-virus/security pack software must work to protect. There are 65, 535 possible IP ports for TCP alone. Add, UDP, ICMP, IGMP, etc.- each with up to 65, 535 possible access ports to be protected! I think you may see the idea.

I have read many messages over the 'net' that others are complaining about MS service packs giving similar problems. Since, I am trying to host my own 'membership' server, I don't mind the slow boot-up, if it means better security. I awake, start my MSW2KP (my server is usually on), fix coffee, have a pastry, brush my teeth, contribute to the 'Ivory Princess' and return. It's been 15 to 20 minutes, and now I can 'login'. <s>

From what you have shown in your message, I believe your issues may be similar and are not a sign of a critical problem. I'm not certain, but, that's my take on it. Happy Good luck!