Windows 2K machines stopped detecting updates

We have 30 Windows 2K SP4 machines searching for updates on a WSUS server.
The 2K machines were configured 4 or 5 a day over the course of two weeks.
When initially detected, they had 70-80 needed updates on average.

Initially, the process seemed to work as expected, with the number of needed
updates slowly heading towards zero as updates were applied in batches and
the machines rebooted themselves on pretty much a daily basis. Eventually we
noticed that SOME machines (about 19) had stopped downloading and installing
updates, with 30-40 updates to go. The rest of the machines are gleefully in
synch.

The windows update logs on the uncooperative clients do not show any errors.
They claim the agents are up to date (IsUpdateRequired=NO). And they claim
that there are no updates are pending ("0 updates detected").

The WSUS Admin webpage lists a bunch of needed, critical updates for each of
these clients, as does the Windows Baseline Security Analyzer.

We've looked on the web for troubleshooting tips for this situation but
cannot find anything. Any pointers?

Here is a snippet from the windows update log, perhaps it might help:
2006-02-16 15:46:57 820 4a0 AU Triggering AU detection through DetectNow API
2006-02-16 15:46:57 820 33c AU #############
2006-02-16 15:46:57 820 33c AU ## START ## AU: Search for updates
2006-02-16 15:46:57 820 33c AU #########
2006-02-16 15:46:57 820 33c AU <<## SUBMITTED ## AU: Search for updates
[CallId = {A008018F-35A8-4257-B37A-11B1DC777AC7}]
2006-02-16 15:46:58 820 40c Agent *************
2006-02-16 15:46:58 820 40c Agent ** START ** Agent: Finding updates
[CallerId = AutomaticUpdates]
2006-02-16 15:46:58 820 40c Agent *********
2006-02-16 15:46:58 820 40c Setup *********** Setup: Checking whether
self-update is required ***********
2006-02-16 15:46:58 820 40c Setup * Inf file:
C:\WINNT\SoftwareDistribution\SelfUpdate\Default\w usetup.inf
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\cdm.dll: target version = 5.8.0.2469, required version =
5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\iuengine.dll: target version = 5.8.0.2469, required version
= 5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wuapi.dll: target version = 5.8.0.2469, required version =
5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wuauclt.exe: target version = 5.8.0.2469, required version
= 5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wuauclt1.exe: target version = 5.8.0.2469, required version
= 5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wuaucpl.cpl: target version = 5.8.0.2469, required version
= 5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wuaueng.dll: target version = 5.8.0.2469, required version
= 5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wuaueng1.dll: target version = 5.8.0.2469, required version
= 5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wucltui.dll: target version = 5.8.0.2469, required version
= 5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wups.dll: target version = 5.8.0.2469, required version =
5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wups2.dll: target version = 5.8.0.2469, required version =
5.8.0.2469
2006-02-16 15:46:58 820 40c Setup Update NOT required for
C:\WINNT\system32\wuweb.dll: target version = 5.8.0.2469, required version =
5.8.0.2469
2006-02-16 15:46:58 820 40c Setup * IsUpdateRequired = No
2006-02-16 15:46:59 820 40c PT +++++++++++ PT: Synchronizing server
updates +++++++++++
2006-02-16 15:46:59 820 40c PT + ServiceId =
{3DA21691-E39D-4DA6-8A4B-B43877BCB1B7}, Server URL =
http://fred/ClientWebService/client.asmx
2006-02-16 15:47:12 820 40c PT +++++++++++ PT: Synchronizing extended
update info +++++++++++
2006-02-16 15:47:12 820 40c PT + ServiceId =
{3DA21691-E39D-4DA6-8A4B-B43877BCB1B7}, Server URL =
http://fred/ClientWebService/client.asmx
2006-02-16 15:47:14 820 40c Agent * Found 0 updates and 9 categories in
search
2006-02-16 15:47:14 820 40c Agent *********
2006-02-16 15:47:14 820 40c Agent ** END ** Agent: Finding updates
[CallerId = AutomaticUpdates]
2006-02-16 15:47:14 820 40c Agent *************
2006-02-16 15:47:14 820 40c AU >>## RESUMED ## AU: Search for updates
[CallId = {A008018F-35A8-4257-B37A-11B1DC777AC7}]
2006-02-16 15:47:14 820 40c AU # 0 updates detected
2006-02-16 15:47:14 820 40c AU #########
2006-02-16 15:47:14 820 40c AU ## END ## AU: Search for updates [CallId
= {A008018F-35A8-4257-B37A-11B1DC777AC7}]
2006-02-16 15:47:14 820 40c AU #############
2006-02-16 15:47:14 820 40c AU AU setting next detection timeout to
2006-02-16 22:35:15
2006-02-16 15:47:19 820 40c Report REPORT EVENT:
{37702C60-536F-4034-B946-750E9CBC78A8} 2006-02-16
15:47:14-0600 1 147 101 {00000000-0000-0000-0000-000000000000} 0 0 AutomaticUpdates Success Software Synchronization Agent has finished detecting items.
2006-02-16 15:47:19 820 40c Report REPORT EVENT:
{CF521432-BF74-4425-B20C-16E7CA1CF8E1} 2006-02-16
15:47:14-0600 1 153 101 {00000000-0000-0000-0000-000000000000} 0 0 AutomaticUpdates Success Pre-Deployment Check Reporting client status.
2006-02-16 15:55:53 820 40c Report Uploading 2 events using cached cookie,
reporting URL = http://fred/ReportingWebService/Repo...ebService.asmx
2006-02-16 15:55:54 820 40c Report Reporter successfully uploaded 2 events.