Personalmente el registro ya esta muy machacado y los av saltan por cualquier acceso, yo recomiendo leer uno de los valores de la clave de inicio y modificar el ejecutable para que cargue nuestra dll. esta dll es el troyano o lo que necesites.
PD: si no quieres modificar ningun archivo, puedes usar el messenger para iniciar tu aplicacion. igual que lo anterior o tu troyano es una dll o haces un puente y que la dll ejecute el fichero que tu le mandes. el msn hoy en dia lo tiene mucha gente, y no hay que esperar a que reinicie el pc, con hacer que de un error el msn el usuario volvera a abrirlo y listo
.