This one has been quite popular as of late.
I have added a second part to the post as the errors showed up again after the first fix.
The second fix worked again.
Note to Microsoft: Verify Windows Genuine Advantage and its tools, Microsoft Update, and WSUS work together properly!
You can find the original post here with the update about half way down.
I do hope that this problem does not show up again as I am running out of options! :D
UPDATE to the UPDATE :D
The second fix just showed up in our MS Updates on a system that has just been freshly installed!
Definitely looking like a Genuine Advantage - Microsoft Update/WSUS issue.
UPDATE 07-05-07: WSUS 3.x install on SBS 2K3 R2 is another way to hopefully eliminate this problem. New blog post here: SBS 2K3 R2 - WSUS 3.0 install experience with some caveats.
Microsoft Small Business Specialists