There's very little that can be easily done about this other than moving your smtpd to an ipv4 address with an ISP that has never had an outgoing spam problem (such as for example a /24 that's been held by the same company for 8+ years, in ARIN/RIPE/APNIC/whatever space very tightly controlled by the network engineering team of a clueful local ISP where you know the staff).
There's a pretty direct inverse correlation between the cost of a hosting service ($5/mo VPS vs. minimum $200/mo colocation of a 1U server) and how much outgoing abuse traffic has been sent from the particular netblock assigned to the enduser customers. Cheap hosting company = poor IP space reputation.