When it is blacklisted, the user/owner of the IP must go to each "anti spam" provider that blacklisted the IP. I.e. spamhaus, they have a page[1] to check if an IP is blacklisted as well as asking to remove the IP from blacklist.
I drop SMTP connections from servers that simply do not have matching forward and reverse DNS. This rule eliminates like 90% of spam. It's a good rule and I won't make any exceptions. There's no way to contact me. Your bounce message tells you what you have to do: get your DNS ducks in a row.
That's assuming your residential ISP even bothers to assign a generic PTR record to your IP.
Even that doesn't work all the time. hotmail is currently bouncing emails from me[0] even though Microsoft's own sender reputation thing[1] says my IP is in good standing.
[0] with a link to [1] just to rub it in.