Reverse DNS - how to correctly configure for SMTP delivery
Solution 1:
What you've got is "forward confirmed reverse DNS" -- that is, the named returned by reverse-look-up, when run thru a forward look-up, returns the same IP as the original IP used in the reverse look-up (see http://en.wikipedia.org/wiki/Forward_Confirmed_reverse_DNS for the more verbose description). That's a good first step.
The rejection messages are your best source of information about why your emails are being rejected. It looks like prod01.bidrodeo.com isn't listed as an MX for the domain bidrodeo.com, and that's going to cause problems with some anti-spam techniques. I would consider configuring the proper TXT record for SPF (see http://old.openspf.org/dns.html) for this server computer and MXs for your domain. That's going to help with some email reception issues.
If you have examples of some of the rejections and have questions about them link them to the question.
Solution 2:
Most SMTP servers will accept your mail if you simply have a reverse DNS entry. It does not have to match the domain name on your e-mail address. Some SMTP servers will reject mail if the reverse DNS doesn't match the HELO/EHLO hostname used in the connection. If your mail server's hostname is mail.example.com then your reverse DNS, MX record, HELO/EHLO, and SMTP greeting banner should all be mail.example.com as well. That server, however, could be providing service for example.com, joes-example.com, and marys-example.com without any problems.
Some other things to consider would be publishing an SPF record in the DNS for the domain name you use to send mail to identify the IP space you send from. Some larger providers look for this and give priority to mail coming from an SPF-enabled domain.
Also, keep an eye on the "reputation" of your IP address through SenderBase, as some providers will delay your mail or apply additional scanning/filtering if your reputation score is too low.
Solution 3:
No, the server name and domain don't need to and rarely do match. Reverse DNS lookups simply ensure that the IP is a PTR record to the server name.
If you can post the headers/bounce messages of an example delayed or reject message, we should be able to narrow down why they're having issues.