hiding files in the startup folder is easy to detect and delete.
try hiding it in the registry under hklm\software\microsoft\windows\currentversion\run as well as hkcu\software\microsoft\windows\currentversion\run

the shutdown command only works if you have the resource kit or support tools installed.but if those are installed you might as well do a kill * -f to close evrything possible hence crippling windows where the user would have to reboot themselves.

if you have access to the machine just change the local administrator account password and use psexec from a remote workstation.

autoexec.bat does not launch with windows since win98,maybe ME, even if it did, shutdown.exe is a windows app which means it will not launch on startup.