Código PHP:
Ver original$mensaje = "Nombre: " .$Nombre. " \r\n";
$mensaje = "Apellidos: " .$Apellidos. " \r\n";
$mensaje = "Ciudad: " .$Ciudad. " \r\n";
$mensaje = "Provincia: " .$Provincia. " \r\n";
$mensaje = "Telefono: " .$Telefono. " \r\n";
$mensaje = "Servicio: " .$Servicio. " \r\n";
$mensaje = "Destinatario: " .$Destinatario. " \r\n";
$mensaje = "Mensaje: " .$texto. " \r\n";
$mensaje = "Enviado el " . date("d/m/y \a \l\a\s H:i:s ");
Estas sobrescribiendo la variable, te falta .= en vez de = tal como lo has hecho con $header.
Saludos.