I think a better way around using telnet is to use another XP command to help with authentication to the remote computer which is the problem here...
runas /netonly /user:\ "shutdown -s -m \\"
The runas command allows you to specify a different user to execute a program that the current user wouldn't have access to. In this case using the /netonly switch targets the remote computer for the authentication.
After executing the above it will ask you for a password for the remote user and it keeps the password hidden from anyone watching.
Hope this helps.