I administrator numerous environments and have never had this much trouble getting machines to check into the console. My WSUS server is off-site and the machines check directly into it. The settings are pushed via group policy and I've verified via registry that it has accepted the group policy and WSUS server. I've tried rebooting as well as wuauclt.exe /downloadnow /reportnow /detectnow. Those steps usually do the trick. I've examined the WindowsUpdate.log and confirmed it is connecting to my WSUS server and looking to be assigned to the "Unassigned Computer" group within WSUS. I have also seen SOME of the workstations at this office check in at random points through the day without issue so it does not appear to be firewall related.
Any assistance on this is greatly appreciated.