Currently I am experiencing a somewhat similar problem. I also run my own mail server and rent a static IP address from the biggest telco here in Paraguay. MxToolBox site shows me that I am flagged by only one, in my case SPAM RATS Dyna.
The instructions on the MxToolBox website are quite clear, first check if there are no viruses and/or malware. Then check if all the records (MX) and proper returns (PTR) are configured correctly on your end and/or by your ISP. Once your done, most of the anti-spam organizations allow you to rid your IP from their list. They will keep an eye on you for a x amount of time, but if nothing happens again in that x amount of time, all goes back to being fine.
At least, that is how the story is supposed to go.
In my case the SPAM RATS Dyna website states that the whole C-block of IP addresses to which my IP belongs is being blocked. And because of that, no option to remove myself from that list is provided.
The telco states that there is nothing wrong at all, so it will be a long time before my IP will be removed. On previous cases the story above did work as intended.
Now, ISP servers make use of those spam list and as there are a lot of list providers, most ISPs only use 2 or 3 of these list. The SPAM RATS Dyna isn't a popular list in Europe, where most of my mail communication takes place, so the spam block hardly affects me. Mail to the US on occasion does bork.
Please take a look at the source of bounced messages, you will see a lot of error codes. Servers usually respond with the reason why a message bounced, but often also provide you with the (exact) name of the list they are using. You could then ask the owner/maintainer of the receiving mail server to make an exception for your IP, or perhaps even persuade them to use a better spam list provider. This might go easier if you can provide them with web shots from the steps you have taken to be removed from that list and the unwillingness of the spam list provider to do so.
The MxToolbox website allows you to create a free account where your IP is periodically checked against a subset of spam list providers to see if there is a problem. You'll have to upgrade to a paid account for the full set. If your server is flagged by multiple spam lists, you have a bigger problem. This would be why you look up mail server responses from bounced mail(s).
Sorry I have no better response, my problems with spam lists have been rather easily solved until now... (knocking on wood).
