Shouldn't a DNS and ReDNS lookup match?

[Dagwood Bumstead]

I have a situation where a mail from our host is being refused by
another mail host.

When running a DNS against our host name, the IP is returned
correctly. But when running a reverse DNS for the IP address, our
uplink provider is returning a completely different host name ending
with their domain name instead of ours. 

They have said they can't change it.

Isn't this an error in their system that they have to change?

===================

In a different, but related situation, to help me understand, I have a
different mail server that is hosted remotely. Pinging the host name
returns the correct IP address, but the ReDNS on the IP returns the
provider's host name (they are both the same machine; same IP
address). How does this affect when some other mailserver does a ReDNS
check to accept mail?

Thanks for any help.