MX Record Issue

[Jonathan de Boyne Pollard]

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.)