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.