on your email server. You should get output like:
dig +short google.com MX
If you do not then something is wrong with the DNS server that you have set your email server to use. If however you do get a response like that then your problem is not that your email server can't find the MX record of a domain to send the email to. I still would like to see whatever line of the logfile you are seeing that tells you that your server can't find the MX record. Are you only having this issue on a single domain you are trying to send to or are all domains having this issue?
If you are only having this issue with a single domain try running some queries on your email server like the following:
This should show what your email server sees as the MX record for domain.tld:
If that returns a result then do:
dig +short domain.tld MX
using the answer you got in the previos query. This will return what address your mail server thinks it should connect to. Make sure that your email server is able to connect to it (Possibly it is getting an internal IP address when it shouldn't?)
dig +short server.domain.tld
Hopefully this will help you.