@slp It could also be that other VPS customers are or have been sending spam, or it was your IP with a previous tenant, or you're newly sending mail from a previously unknown IP.

At the risk of giving unsolicited advice, maybe try getting your VPS provider to ask? Or checking the public blacklists for your IP? Or using an smtp health check service? Even something as a mild DNS typo could mess you up.

Good luck, mail is increasingly more of a pain for the small server with each passing year.