(Nota: Eu sei que isso é quase 3 anos de idade, mas eu cheguei nessa página pesquisando uma pergunta semelhante, então estou escrevendo a resposta correta aqui para qualquer outra pessoa vindo aqui)
Sim, é possível, é mesmo preferível fazer isso em vez de sobrecarregar a variável PATH. Você precisa adicionar uma chave na chave de registro HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\App Paths
(para a máquina) ou HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\App Paths
(para o usuário - preferencial).
O formato é o mesmo em ambos os casos, o nome da chave deve ser utility-5.exe
e o valor padrão do registro deve ser D:\utils\utility-5.exe
.
Existem mais informações (incluindo várias outras coisas que você pode fazer) no MSDN e por Raymond Chen