Bueno, como no sé qué control voy a tener sobre el server en el que va a estar la aplicación, terminé usando cURL:
Código PHP:
$curl = curl_init('https://www.sandbox.paypal.com/cgi-bin/webscr');
curl_setopt($curl, CURLOPT_POST, true);
curl_setopt($curl, CURLOPT_RETURNTRANSFER, true);
curl_setopt($curl, CURLOPT_POSTFIELDS, $req);
$res = curl_exec($curl);
Funciona. Devuelve Invalid, pero eso es lo de menos, el pedido funciona. Ahora me fijo qué está mal.
Gracias
Fede!