MX Record Issue

[John]

Currently the company hosting our DNS has it configured something like the
following (I can't do a zone xfer and I'm trying to get a copy of it. This
may contain typos but I'm just attempting to show the records contained in
DNS currently) -

@    86400                IN    SOA       ns.company.com.
root.company.com. (
                                            3000
                                            10800
                                            604800
                                            86400
                                    )
                                  IN    NS          ns.company.com.
                                  IN    NS          ns2.company.com.
                                  IN    NS          ns3.company.com.
                                  IN    NS          ns4.company.com.

mail.company.com.     IN    A            123.123.123.123
www.company.com.   IN    A            234.234.234.234

company.com.            IN        MX        10        mail.company.com.

Our mail addresses are username at mail.company.com. I'm not sure why, it was
setup before I arrived. This goes back years. We're now having a problem
with a particular company where they cannot send email to us because there
isn't an MX record for the 'sub-domain' mail.company.com. They are running
an SMTP server from Tumbleweed.com, and they are using RDNS lookups to cut
down on SPAM. Our Internet provider for some reason doesn't have any PTR's
defined, I'm guessing because no one here asked them to. (I've only been
here < 2 months).

I've modified our mail server so that each user has an aliased email address
of username at company.com. If that email address is used, then the company
above doesn't have a problem. The error that they are getting from their
tumbleweed software, which apparently started rejecting sending mail to us
recently (~ 2wks ago), is that it can't find the MX record. I'm thinking
that they changed something, but I've been told they haven't.

So, to fix this on our end, I believe I need to have the DNS hosting company
(despite protests from their support staff that it's definately not req'd)
add another MX record something like this -

mail.company.com.      IN        MX        10        mail.company.com.

And I need to contact our ISP, and have them add a PTR record for our mail
server.

I'm going to be adding a 2nd mail server in the next couple of months, so at
that point, I'd have (2) more MX records and an additional A record added,
with a lower priority pointing (100) to that server.

Am I missing something obvious (outside of typo's that I may have made in
the above example)? Is the additional MX record required?

Thanks.

John