Versions Of Windows Update And Microsoft Update Have Been Malfunctioning ..
.. for some time.
I am still supporting Windows XP Pro SP3, and one of the systems with that on did not signal that the May 2012 SB updates were available until 24 hours after they had been released to the general public (despite connection to the internet during that time).
Worse still, Windows Update on the same (and other Windows XP) systems continues to nag that some SB patches need to be applied after the patches have been performed. That nag will persist even after one or more explicit executions of Windows Update or Microsoft Update.
[This malfunction has been present on all the Windows XP Pro SP3 systems that I support for the better part of a year. It is suspected to have been introduced by some other SB patch performed during that time, or because the Windows XP version of the Windows Update and Microsoft Update products haven't been properly updated to take account of other SB patches since the malfunction started.]
As for MS's use of digital certificates for SB patches, I haven't seen any evidence of that use on fully up-to-date versions of Windows XP Pro SP3. (That may, of course, be because all the patches that I apply do have suitable digital certificates.)