Hi @Mihai Mihaiescu I'm glad that you were able to resolve your issue and thank you for posting your solution so that others experiencing the same thing can easily reference this!
Since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others ", I'll repost your solution in case you'd like to "Accept " the answer.
Issue :
Your ACS domain configured correctly everything and everythingwas validated but you kept getting your emails failed with the error "MailboxNameNotAllowed"
Solution :
After investigating this issue you confirmed that it was Azure related. You discovered that some enterprise servers reject your emails if the subdomain from which the email comes even though it is valid in ACS. So in order to send emails from a custom domain, you don't have to pass only the ACS validation rules and Azure recommendations, but you also have to do this A setting for the subdomain, to a valid IP.