Another option would be to make your windows service dependent on another windows service for example the network service. Check the dependencies tab on an installed windows service.
You can program this in the service installer. Below is an example.
using (ServiceProcessInstaller processInstaller = new ServiceProcessInstaller())
{
processInstaller.Account = ServiceAccount.LocalSystem;
processInstaller.Username = null;
processInstaller.Password = null;
using (ServiceInstaller installer = new ServiceInstaller())
{
installer.DisplayName = "My wonderful windows service.";
installer.StartType = ServiceStartMode.Automatic;
installer.ServiceName = "MyService";
installer.ServicesDependedOn = new string [] { "COMSysApp" };
this.Installers.Add(processInstaller);
this.Installers.Add(installer);
}
}