mcavic - 8:42 pm on Feb 10, 2010 (gmt 0)
The company that owns your IP address (the VPS host) needs to make the change. Tell them that you want to change your Reverse DNS entry, so that x.x.x.x points to mail.yourdomain.com (as long as mail.yourdomain.com is valid).
Most likely they just didn't know what you were asking. But if they absolutely refuse to change it, you may be able to forward your outgoing mail through their mail server.