PTR meint hier DNS-Reverse, oder?
Ja, im DNS wird für die Auflösung von IP zu FQDN ein PTR Eintrag vorgenommen.
Ist damit gemeint, dass ich im Plesk auch den hostnamen ändern muss?
Sinnvollerweise ja, damit es überall einheitlich ist.
Aber jetzt gesondert für mail ist doch mein MX Record verantwortlich, oder? Mein MX-Recors geht momentan auf mail.domain.de (und für mail.domain.de habe ich auch A+AAAA Records gesetzt) Bleibt MX auf mail.domain.de?
Der MX-Record ist nur für den Mail-Empfang verantwortlich, also für Mails, die an deinen Server geschickt werden. Das kannst du halten wie du willst, beides wird funktionieren. Das einzig wichtige ist, dass ein MX immer auf einen A-Record zeigen muss, nicht auf einen CNAME oder eine IP-Adresse.
Die Änderung des FQDN ist hingegegen für das Senden von Mails, damit andere Server diese von deinem Server annehmen und möglichst nicht als Spam markieren. Wichtig ist auch die Änderung des HELO, mit dem dein Mailserver sich bei anderen meldet. Ohne Plesk kann man diesen in der /etc/mailname oder /etc/postfix/main.cf setzen, aber Plesk überschreibt diesen wahrscheinlich. Daher musst du mal schauen, wo du diesen in Plesk setzen kannst. Wenn nix in den Dateien konfiguriert ist, verwendet Postfix den vollqualifizierten Hostnamen.
Bezüglich des Hostnames im System selbst (die /etc/hostname und der hostname Befehl) wird dieser wohl von Strato auf Grund der Virtualisierungslösung beim Booten wieder auf den von Strato vorgegebenen Namen zurückgesetzt. Es gibt ein paar Workarounds (einen hast du ja schon gefunden, ist aber für upstart), da musst du schauen, welcher zu deinem Init-System passt (SysV-Init, Systemd, usw.)