1)Restart the automatic update service.
2) Run "wuauclt /detectnow", run "wuauclt /reportnow", wait a ten minutes.
3) Can you find anything related in the event log of the problematic machines?
4) At the wsus server check if these machines have one or more "failed" updates. (I once had a few notebooks which repeatedly failed at WinXP SP3 until manual intervention)
5) Check (compare with functioning counterparts) if anything has changed in the registry (inside HKLM\SOFTWARE\Policies\Microsoft\windows\WidowsUpdate)
6) Are there any other differences (could even be DNS problems)?