Buen dia, claro que se puede instalar un programa en Recovery y tambien hacer que se autoejecute al cargar windows. En caso de formatear la particion del sistmema operativo el programa seguiria viviendo en Recovery a menos que formatien tambien esta partición, El problema que veo es que si desicen formatear el sistema operativo se perdera el registro o ejecutable que arranque el programa guardado en Recovery. se me ocurre hacer un autorun en la particion oculta que es como funcionan algunos virus, pero este iniciaria solo al intentar entrar a Recovery.
En caso de que los ladrones no la formatien es todo facil
Saludos!