I have multiple websites running on each droplet though.

If I understand what you are suggesting, while this would solve the issue for one domain the others would still suffer.

Thanks for spending so much time on this though BTW.

You can set the droplet's hostname (which would update the PTR record along with it) to e.g. mail.yourdomain.com where yourdomain.com is one of the domains on that droplet, and then add an A record for mail.yourdomain.com that points to your droplet.

This way it's a valid PTR <=> FQDN setup and it will work fine for all of the domains on that droplet.

Are there PTR records listed in your DigitalOcean Control Panel?

Only the ones setup by digital ocean which point to the hostname of the VPS.

e.g.
xxx.xxx.xxx.xxx -> server a
xxx.xxx.xxx.xxx -> server b

and it's the domains that do not form the FQDNs of your droplets that are bouncing?

I don't have any domain names in the PTR record in the DO DNS section. I named my droplets with unique names when creating them.

So yes thats correct but by default really - as none of the domains form the hostnames of my droplets :-).

Log into your DigitalOcean Control Panel and click on Droplets => Settings => Rename for each droplet and rename it -- incorporating your domain name so that you end up w/a FQDN, e.g. hostname.yourdomain.tld

Excellent, thanks very much for your help Kamal and Pablo!

Thanks by the advice.
Just only one question, what about the /etc/hostname file? set it with the same name of the droplets or it isn't necessary?

It should already be set to your droplet's hostname however you can modify it anytime you want and then run

sudo hostname -F /etc/hostname

for the changes to apply.

@victor.andres1: Check out Setting the Hostname & Fully Qualified Domain Name (FQDN) on Ubuntu 12.04 or CentOS 6.4 | DigitalOcean.

so does my hostname need to be mail or mail.domain.com? does my droplet need to be named mail or mail.domain.com? i started following the link that pablo posted, but it is also not clear there if the hostname is mail or the full mail.domain.com.

i also need to server mutliple domain names with a single droplet. i made my droplet named "mail.domain.com" (with one of the domains on the droplet instead of domain.com)

then added an A record to that domain's dns record with value mail and my ip address.

how can i test if my reverse dns is working?

@billy: mail.domain.com sounds good. You can test if reverse dns is working here: http://mxtoolbox.com/ReverseLookup.aspx.

So I set this up and it appears to be working -- but what about MX records... do I need to set those up as well? I'm going to have multiple domains on one droplet.

@Kamal I understand what you are saying here:

"You can set the droplet's hostname (which would update the PTR record along with it) to e.g. mail.yourdomain.com where yourdomain.com is one of the domains on that droplet, and then add an A record for mail.yourdomain.com that points to your droplet."

However I am confused how this works for multiple domains on the same droplet. For example I have example1.com and example2.com on the same droplet and I want to setup email on both domains. Do I therefore name my droplet mail.example1.com and setup an A record for mail.example1.com and mail.example2.com pointing to the same place and then everything works with reverse DNS? Or have I completely misunderstood you?