Quando você executa java.exe em seu exemplo, o shell pesquisa apenas o diretório atual (ou seja, \RemoteMachine\C$ ), mas não seus subdiretórios. (Em outras palavras, é mais parecido com dir java.exe sem o /s .)
Como não existe tal arquivo na C:\ da máquina remota, a próxima etapa é pesquisar os diretórios especificados na variável de ambiente %PATH% (que normalmente contém apenas diretórios locais).
Para resolver seu problema, especifique o caminho completo para java.exe . Você nem precisa usar pushd :
C:\> "\RemoteMachine\C$\Program Files\Java\jre6\bin\java.exe" -version