Changing server mail address (hostname?) on VPS (parallels, plesk)

Modern major mail services score spamminess based on multiple reputation factors, if available.

If the only factor is your IP and you don't mail often, this might be "the reputation of the /24 my IP is in". If you mail a lot, you might get your own reputation.

The easiest way to get reputation which "drowns out" the IP reputation of your netblock is to set up DKIM. Send your mails signed. This will establish a per-domain reputation, instead of per-IP reputation, and provides more signal to the automated scoring systems.

The more you work to help the recipients of your email figure out who you are and how trustworthy you are, the more signals they have to work with and the better a job the automated systems can do in deciding that you're legitimate, unlike whoever else bought a virtual machine in the same netblock, pumped out spam and then left, bills to hosting service unpaid and everyone else's reputation tarnished.

[some years later]: I wrote a blog post a couple of years back, walking through a lot of the steps needed to be able to more reliably send to large mail providers: https://bridge.grumpy-troll.org/2020/07/small-mailserver-bcp/

The email protocol is totally insecure. Anyone can set the From line to anything they want, and there's basically nothing you can do about it.

These people don't need access to your email account - they just send the emails from their own servers, setting the From line to whatever they want.

You get the bounce messages because the receiving servers simply follow protocol and send an error report to the From / Reply-To address.

If you examine the Received headers from the original message, you'll see the messages were never sent from the Google servers.

There have been attempts, such as DomainKeys, to provide systems that allow people to verify that an email was sent by the reported sender, but these completely rely on the receiving servers implementing them. At best, many servers only implement these systems to help mark spam.

Welcome to the Internet