SMTP Issues - Host or domain name not found - Encountered via trustwave Mailmarshal Email SEG

Ok, so we have that issue that the gateway is unable to deliver via MX or even relaying to the MX hosts directly. To make the story short, we found out that the gateway host was restricted, and we requested to allow SMTP port outgoing to ANY ANY. Still not able to, so the additional port needed was... port 53 (DNS) TCP/UPD, allowed to any any. It works.