Hola,
Yo en casos como el que comentas lo que hacía (y puede que no sea mala costumbre) es que desde el principio, desde la primera instalación, creaba una clave en el Registro de Windows con la versión (y lo que se te ocurra) de la aplicación que estaba instalándose.
Claro que esto a ti no te servirá ya de mucho, puesto que lo que digo es que de ese modo, haciéndolo así, es trivial con el
InnoSetup comprobar si una determinada clave del Registro de Windows existe. De todos modos, aunque no dejaras algo "preparado" de antemano, tal vez podrías utilizar alguna otra clave del Registro, en caso de que tu aplicación guarde "cosas" ahí.
Por otro lado, creo recordar que InnoSetup permite "incrustar" código de Object Pascal en el instalador, o sea, no todo pero sí un subconjunto de funciones y eso. Tal vez, si no te queda más remedio, podrías tratar de buscar, directamente, el ejecutable de tu aplicación. Esto ralentizaría la instalación del programa, pero, a lo mejor se puede hacer algo para evitar que fuera eterno.
Me refiero a que acaso no tengas que buscar en todo el disco duro, sino, sólo en determinadas rutas. Y, por otro lado, en este tu segundo instalador, no te olvides de incluir ya una "marca" en el Registro de Windows, de modo que desde un tercer instalador de tu programa pudieras comprobar si dicha marca existe o no.