After some digging here are the results I came up with. The IT Administrator who originally setup the network did so through ghost imaging. In doing that, sysprepping his original source image wasn't in his list of steps. That being the case, some of the registry keys specific to Windows Update that sysprep clears were inherently not cleared properly.
Fixing this issue is a pretty simple registry edit for each computer. First, make sure that the Automatic Update service is stopped. Open up regedit, and browse to HKLM\Software\Microsoft\Windows\CurrentVersion\WindowsUpdate. From here, delete the PingID, AccountDomainSid, and SusClientId entires. After doing this, start the Automatic Update service again, and at a command prompt, type "wuauclt.exe /resetauthorization /detectnow". This should make the computer show itself in the WSUS console
Chris Sanders is a network consultant for KeeFORCE, one of the most popular network consulting firms in western Kentucky. Chris is the author of the book Practical Packet Analysis as well as several technical articles. His personal website at www.chrissanders.org contains a great deal of information, articles, and guides related to network administration, network security, packet analysis, and general information technology.