O mais provável é que o executável seja iniciado a partir do link simbólico com seu atual diretório aquele em que o link simbólico reside, em vez daquele em que o executável reside, portanto, as DLLs no diretório do executável não são encontradas.
Concordo que, de acordo com a definição do algoritmo de pesquisa, dada por Microsoft, as DLLs deveriam ter sido encontradas. Esta é provavelmente uma deficiência no algoritmo de procura de DLL do Windows e não há nada que você possa fazer sobre isso.
Uma solução alternativa seria usar outro mecanismo que o symlink,
armazenar na pasta Path um arquivo .bat
em vez de um symlink.
O arquivo seria algo como:
cd \path\to\exe-folder
exe-file