Mail server cannot send email to a specific domain

[JRR]

This may not be the place for this and I'm not a DNS pro (although I
understand the concept and can setup simple DNS entries), but I'm not sure
if this is DNS related or not, so here goes...

I have a Windows based mail server that has a really tough time forwarding
emails to a particular domain that is hosted by a hosting company.  The
receiving domain hosting company assures me there are no problems on their
end, but I'm not so sure.  I am also unable to forward emails to the hosting
company themselves.  My mail server SMTP log shows timeouts connecting to
the receiving mail server.  Every now and then a message will get through.
Connectivity is not an issue.

I started checking things out and initially found the receiving domain MX
was referencing a CNAME entry.  They fixed this, but still no go.  Then,
there was no reverse DNS entry for the receiving MX.  They fixed this too,
but I have a question about this one.

I'm told by the mail server manufacturer that the reverse DNS entry for the
receiving domain MX should reference the mail server itself or the exact
problems I'm seeing can happen.  This is an example of how the reverse DNS
entries are setup for the subject domain:

Mail server manufacturer says it SHOULD look like this (which is the way I
usually see them):

x.x.x.x.in-addr.arpa mail.receivingdomain.com.

In the case of the subject domain, the reverse DNS entry looks like this:

x.x.x.x.in-addr.arpa hostingcompanydomain.com.