Ya encontré el error. En local, la ruta tiene que tener doble '\', pero para la ruta externa esto falla por lo que no hay que duplicarla.
Lo siguiente ya me funciona:
Código:
set FECHA=%date%
set FECHA=%FECHA:/=%
set FECHA=%FECHA: =%
set FECHA=%FECHA::=%
set FECHA=%FECHA:,=%
set FILE= \\192.168.1.25\BKPs\Backup_db_%FECHA%.sql
C:/AppServ/MySQL/bin/mysqldump.exe -hlocalhost -P8080 -uUsuario -pPassword -e -c -r%FILE% NombreBBDD
-h, como comentaba, efectivamente se refiere a la máquina donde está mysql no la máquina de destino donde almacenar el archivo. Aquí puse localhost pero se puede obviar porque es el valor que tiene por defecto.
Un saludo!!