I've encountered this sort of thing before in Windows 2000. In the end, I resort to the following 'reset' batch file. I've always found it to kick Windows Updates into action:
net stop bits
net stop wuauserv
del /f /q %windir%\WindowsUpdate.log
del /f /s /q %windir%\SoftwareDistribution\*.*
%windir%\system32\regsvr32.exe /s %windir%\system32\atl.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\jscript.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\msxml3.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\softpub.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\wuapi.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\wuaueng.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\wuaueng1.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\wucltui.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\wups.dll
%windir%\system32\regsvr32.exe /s %windir%\system32\wuweb.dll
net start bits
net start wuauserv
wuauclt /resetauthorization /detectnow
I shouldn't think it'll be too different for XP - if at all.