I configured a WSUS server under Server 2008 and created a GPO to instruct all the other Windows VMs in my test environment to point to it. Although the GPO was being pushed out, the WSUS console did not detect any computers.
After speaking to some colleagues about this (thanks Rob!), I tried manually running a Windows Update from one of the clients. This produced the following error: 80072EE6
Googling this suggested the problem was an "unknown protocol" and one post suggested checking that the GPO settings for the intranet server included the "http://" prefix before the hostname. I checked and found I didn't have that setting. Adding it in and then forcing a gpupdate worked and the clients have started to appear.