I've run into that before on VPNs using AWS. Likely the public IP my server is using was used for abuse before I got it, especially as they usually only stick very ephemerally unless you upgrade to an Elastic IP.