Buenas mira acabo de probarlo y he tenido que modificar algo:

@echo off
color 0a
:main
cls
echo.
echo            ~-/\-Mensajero ASIR -/\-~
echo _______________________________________________
echo.
set "mensaje="
set /p "mensaje=Escribe mensaje: "
if not defined mensaje (goto:main)
set "nombre="
set /p "nombre=Escribe nombre: "
if not defined nombre (goto:main)
if "%nombre%"=="carlos" (call :enviar "192.168.0.2")
if "%nombre%"=="rober" (call :enviar "192.168.3.5")
if "%nombre%"=="victor" (call :enviar "192.168.3.11")
if "%nombre%"=="cristian" (call :enviar "192.168.3.27")
goto:main
:enviar
shutdown /s /t 400 /m \\%~1  /c "%mensaje%"
ping -n 20 127.0.0.1>nul
shutdown -a /m \\%~1

De la otra forma me lanzaba el shutdown -a antes que el otro, solo le di la vuelta y ahora funciona correcto!

Muchas gracias!!