Obrigado ao @DavidPostill por me guiar na direção certa.
Eu fiz um arquivo de lote como sugerido, usando a seguinte pergunta em stackoverflow como base: link
Veja o que eu criei:
SETLOCAL EnableExtensions
set EXE=MyProgram.exe
FOR /F %%x IN ('tasklist /NH /FI "IMAGENAME eq %EXE%"') DO IF %%x == %EXE% goto FOUND
start C:/path/to/MyProgram.exe
:FOUND
Em seguida, alterei a entrada do registro para apontar para esse arquivo em lotes, em vez do próprio executável.