I believe SarinMage may be on the right track. Check the date for the machines which don't work with WindowsUpdate. The reason is, Microsoft is planning on moving to v5 of WindowsUpdate (at which point, the unsupported OSes will no longer have access to the site). The problem, is, if your date happens to be past the date where the change will occur, WindowsUpdate will not function properly for version 5 has not been completed yet.

AJ