Acontece que o comando estava de fato funcionando como esperado, mas as alterações do registro estavam sendo substituídas pela política de grupo.
C:\PSEXEC \mechaflash -u admin -p admin cmd.exe /C "REG ADD HKLM\SOFTWARE\Policies\Microsoft\Windows\WindowsUpdate /v WUServer /t REG_SZ /d http://WSUS_Server:8530 /f && REG ADD HKLM\SOFTWARE\Policies\Microsoft\Windows\WindowsUpdate /v WUStatusServer /t REG_SZ /d http://WSUS_Server:8530 /f && SHUTDOWN -r -t 00"
O comando declarou que foi concluído com êxito e a máquina remota foi reinicializada. No entanto, as alterações no registro não ocorreram de fato.
Os comandos cmd foram testados localmente e funcionam bem.
Esta é uma questão de privilégio?