To change the hostname on your server, just follow
http://www.rackspace.com/knowledge_c...ostname-change
Are you using a control panel like cpanel or plesk? Both of those have provisions built in for changing the hostname.
The reverse dns will need to be set with your host. It looks like your hosts account portal has the ability to set the rdns for your IP. This is where you would do that:
http://i.imgur.com/TtM2Xt0.png
According to the blacklist entry, your hostname is set as 94-23-78-68.ovh.net. Just set it to a fully qualified domain name, then set the reverse DNS for that IP to match the hostname. There's no need to pay a server admin for this at all.