Por lo que dices, lo que se ha creado no es una copia del ejecutable sino un acceso directo, es distinto de los normales porque es de un programa de 16 bits (de DOS). Lo que dices de config y autoexec no son entradas del registro, sólo le dicen a Windows dónde buscar los archivos de configuración para ejecutarlo.
<p>La verdad es que no estoy seguro, podrías preguntar en otra página más técnica. De todas formas prueba una cosa, pincha en el menú Inicio > Programas > Accesorios > Símbolo del sistema, e intenta borrarlo desde ahí poniendo su nombre de 8.3 caracteres en vez del largo. Si no sabes cómo se hace, dime dónde tienes lo que quieres borrar (¿por ejemplo en el Escritorio?) y qué nombre tiene.