What I'm seeing across a lot of machines is hit or miss updates. Given how close we are to the end of XP I doubt this is going to be fixed.
-> Let's note the OLD FASHIONED WAY to get those updates. Note the KB123456 or KB1234567 and then google that KB number. You may find more detail about the update or a download which you can fetch and install manually.
It's also worth noting that Microsoft has for years suffered us with update issues. It's never been perfect and pains folk that expected it to "just work."
About a month ago, my Windows Update stopped giving me notifications of updates, and when I do attempt updates, they download, but don't install. Now if I set updates to automatic, some of the updates install when I shut down my pc.
I have WinXP (SP3). I have run Malwarebytes, SuperAntiSpyware, Avast (which was my primary anti-virus, but has been replaced with Panda Cloud Free) and Spyware Terminator. I've tried serveral different 'fixes' I've found on this site, and others. Nothing works.