100% mailing have bounced : validation failed for
So I found the problem.
Thanks to @HomoTechsual who lead me in the right direction.

The reason had been found in the Settings - Outbound Mail.
It was set to mail() with a success message : Your SENDMAIL settings are correct. A test email has been sent to your email address.
That looked good but in fact the message was never sent by the server ! Trusting this message, I did forget to check if the test email really arrived to email address. My mistake : always double check.

After I changed the setting to SMTP with all the right setting of the mail server, I still got the success message but the message arrived in the mailbox.
After I removed the bounce tag for each email address, I could make a test mailing that went fine this time ;-)

So the issue was from the mail server. The issue was not with CiviCRM. Something probably related to the DNS is not working on the server. This made CiviCRM confused about the mailing. 
From now Civimail works well with the SMTP set in the Settings - Outbound Mail. I the case of my server this is the only option.

UPDATE : In this case it seems that a group of several issues happened.
I found another thing that could be at the origin in the table civicrm_mailing :
both from_name and from_email are set to (INVALID)

from_name From Header of mailing (INVALID)
from_email From Email of mailing (INVALID)


Yet I have no clue how this happened but there now a clear link with validation failed for &lt;(INVALID)&gt;
I did not find why chosen email provoque that. It might be related with multi-site extension. Now I can manage the mailing with an another email address.