@Tetzo,
Danami just beat me with his answer, he is (to a large extent) correct and has answered your question, if I am not mistaken.
The PTR record is to associate an IP address to a hostname (in contrast to an A record) and is often handled by the hosting provider.
The PTR record is (in essence) irrelevant for your mail traffic.
However, changing the hostname (for instance, via Plesk panel) often does the trick (and does not result in problems with mail traffic).
In fact, the above is the solution to your problem.
But then there is this "issue" with Plesk, the above should be considered to be a partial solution to your problem.
After all, remote mail servers trying to deliver mail to your server want to "know" your server´s location, i.e. IP address.
A good solution is to add an A record, pointing a domain name (equal to the hostname) to the IP assigned to your server, allowing for remote mail traffic to reach your mail server.
And that is all the explanation needed for the (full) solution in question.
Hope the above clarifies the whole thing!
Regards....