Hola.
Yo la vez que tuve que hacer algo asi lo que hice fue haces en vez de una aplicacion windows un servicio windows que te permite crear un servicio que apenas se inicia windows queda recidente.
Fijate si te interesa este tutorial:
http://liarjo.spaces.live.com/blog/c...029!2774.entry
Sino lo otro que podes hacer es agregar una clave en el registro de windows para que lo inicie, pero mejor sería si usas un servicio