I think that IP address reputation is the biggest factor in mail deliverability for small servers. So when you've bought new VPS, it will be hit or miss, whether your IPv4 address was used maliciously before or not.