Eliminar el ejecutable no parece sencillo. Eso sí, puedes modificarlo e incluso puedes renombrarlo. Para ello debes cerrar todos los handles que haya abiertos al fichero. Había un código dando vueltas por ahí... si lo encuentro lo posteo. Es básicamente lo que hace el Unlocker.