I just received this as a failure notice.

Connected to 80.XX.XX.100 but greeting failed.
Remote host said: 554 SMTP service not available (Connection refused for xxx.myipaddress.xxx: no reverse DNS entry. Please inform your ISP/IT department to get your servers updated.)

i'm running a plesk server with qmail, and any ideas how to fix this one?

You need to submit a trouble ticket to RS and ask them to add a reverse DNS emtry (PTR record) for your server. The mail server you're trying to reach tried to resolve your IP address and it failed.

what if I'm controlling my own name servers ? how would I do this?

You still have to submit the TT to get the PTR added, as they have to do it on thier end.

You still have to have RS do it. They don't delgate control of their reverse zones to customers, so they are the only people who can change it.

If you were running your own name server off of RS and you were delegated authority for a block of IPs, you would add a PTR record for your host to the in-addr.arpa zone on your server. It would look something like this in a BIND zone file:

216.127.75.xxx IN PTR server.foo.com.

where server.foo.com is what you want your IP to resolve to.

When someone does a reverse-lookup of your IP, it looks in the in-addr.arpa zone. For instance, if your IP is 216.127.75.xxx, to find the hostname you would look up xxx.75.127.216.in-addr.arpa. The IP is listed backwards so that authority for the zone can be delegated from the top down. A quick seach of google found this site which looks like it might have a decent overview of how it all works.

Anyway, I'm assuming you are a RS customer, in which case they will have to do this for you.