I'm on Digital Ocean, which is basically similar to Linode. You can just get a new IP and maybe have better luck. That is employ the "V" in VPS. For a brief period you will be charged for two VPS. Digital Ocean charges by the hour (like a seedy motel). Probably Linode is similar.
The reason I haven't done this myself is I need to do the DNS setup again for the new IP. I'm on a seldom used RBL called spamrl.com. Truly incompetent organization. I tell them that I'm clear on 90+ RBLs, but they don't care. Their system is perfect. ;-) But I can pay 20€ a month to be on a white list! Spamrl.com isn't even on the mxtool checker. Original Message From: Alice Wonder Sent: Tuesday, December 27, 2016 11:32 PM To: Postfix users Subject: Avoiding spam blacklists Virtual machine for a web application, it is still in testing. reverse DNS is properly set up. Postfix only listens on the local host. Linux firewall drops anything not to port 80, 443, or a custom high number port I use for SSH. This postfix is not an open relay, or a relay for anything on the Internet, it only exists so the web application can send e-mail. SPF for the domain is correctly set up, DKIM for the host is correctly set up, when it sends an e-mail and I inspect it - it passes the rDNS, SPF, and DKIM checks. So far it has only sent e-mails to addresses I control as the web application is still in testing. Yet yesterday the IP address ended up on Spamhaus blacklist. I am 100% confident that no one else was sending e-mail from that IP address, I'm a bit puzzled as to how the IP address got added to the blacklist, but I was told that Spamhaus sometimes just adds an entire subnet if more than one IP on the subnet was sending spam, and that's probably what happened. I think that is irresponsible of Spamhaus if that is what they are doing, but is there something more I can do other than correct rDNS, SPF, and DKIM to avoid getting on a blacklist?