I have multiple Windows agents that are being launched as services.
When I updated Jenkins from 1.495 to 1.506, all the slaves died - they just failed to launch, even though they did it without issues during regular Jenkins restarts.
In order to bring the agents back to life, I had to remove the services from each Windows host ("sc delete jenkinsslave..."), manually remove the agent directory (containing the .jars and .exe), and then create the service from scratch.
If I skip any of the described steps, the agent fails to launch.
Agents are running Windows 2003 Server and Windows 2008 Server, the behavior is identical.
Difficult to investigate this long ago, but generally, you need to make sure that the "slave.jar" file is always up to date. The VersionColumn Plugin can help you determine that (and takes slaves with outdated slave.jar offline).