Re: MX Record Issue

J> [...] they cannot send email to us [...]
J>
J> mail.company.com. IN MX 10 mail.company.com.
J>
J> Is the additional MX record required?

No. The "Tumbleweed" software that your correspondents are using is, if
it really requires this, broken. (And if it's sending mail to you it's
an SMTP *client*, not an SMTP *server*, by the way.) It is not obeying
the algorithms specified in RFC 2821 section 5 and in RFC 974, as it should.

Suggest to your correspondents that they buy software that operates
properly, and that they take the broken software that they have back to
the vendor for a refund.

J> [...] they are using RDNS lookups to cut down on SPAM [...]

This is irrelevant to the task at hand, which is *them* sending mail to
*you*, not the other way around. (The daft and useless reverse lookups
are done by SMTP Relay servers, not by SMTP Relay clients.)