Efectivamente no está sujeta a IVA la cantidad que el francés debe pagar de indemnización por costas, pero no por ser francés, sino por ser indemnización por costas:
http://petete.minhap.gob.es/Scripts/know3.exe/tributos/consulta/texto.htm?NDoc=19371&Consulta=.EN+FECHA-SALIDA+%2809%2F03%2F2005%29&Pos=0&UD=1
Además, la relación económica no es entre tú y el francés, sino entre tu cliente y el francés.
Y tú además, tienes otra relación económica, de cuantía similar o equivalente, con tu cliente.
Sobre la notificación de un NIF-IVA comunitario, más que el tuyo sería preceptivo el suyo, en el caso.
Tú, como prestador de servicios español, SIEMPRE debes recaudar IVA en todas tus prestaciones de servicios sujetas, SALVO que por reglas de localización, puedas ubicar el lugar de la prestación del servicio fuera del territorio.
Tal cosa sucede si es EL CLIENTE el que te notifica un NIF-IVA no español. Entonces ahí si puedes acogerte a no repercutir el IVA español.
Y naturalmente, si se diesen estas operaciones intracomunitarias (que en una condena a costas no se da), deberías hacer el modelo 349.
la plus belle des ruses du Diable est de vous persuader qu'il n'existe pas!