Sending via a VPS is not the same as sending through the VPS provider's email servers. Providers usually have their own outgoing SMTP servers for their clients with people who make sure that deliverability is always working, so sending through those is much more likely to work than sending directly from a VPS.

You said through a VPS. Not the VPS provider's email servers. And you suggested Linode. It looks like you can't send through their servers.