MX records at domainprovider are correct ?
If set, check that your mailserver has a smaller number in priority list
e.g. maildomain.tld MX 10 YOUR.COW
mail.domain.tld MX 20 backup at ISP
AAAND ofcorse, ports smtp, smtps and submission open at firewall?
please give a little more detailed info.