Wenn die .exe in einem Unterverzeichnis des Ordners mit der .bat ist, kannst du relative Pfadangaben verwenden.
Bsp: Batch-Datei in C.\Programme\Beispiel\; .exe in C:\Programme\Beispiel\Data
Dann kannst du in die Batch amstatt "C:\Programme\Beispiel\Data\Programm.exe" auch "Data\Programm.exe" verwenden.
Wenn dem nicht der Fall ist, fiele mir persönlich nur der Weg über die Registry ein. Frag mich aber nicht, wie das zu bewerkstelligen ist...