Examining the logs in the build agents directory, I found an error message:
Unable to ping agent Andromeda. Please check firewall on agent machine
(Andromeda is the name of the Vista PC)
Well, I tried turning off the firewall altogether without any effect.
As it turns out this is a problem due to the fact that the PC has multiple IP addresses and the agent starts listening to the "wrong" one by default. You can override the IP address by specifying it during the install procedure, or later by changing the config file.
Adding this line to the config file solved my problems:
After a short while the build agent showed up on the server, and after authorizing it, everything worked as expected. Hujja for TeamCity!