Just like I should have with my garden, rather than replant among the weed seeds and spend 99% of my time pulling weeds, I would recommend sowing a new field by moving your outbound e-mail server(s) to some fresh address space (different /24 to be sure, ideally another section of SWIPed space) and start monitoring your outgoing servers logs. You'll need to work with each MTA that blocks your e-mail and ask them to delist you from whatever block (domain or domain reputation) that they have. At the same time, systematically go to every RBL that tracks by domain name and check the status of your domain and request delisting as necessary.
if the ipv4 free pool run-out produces a lot of address shifting and recycling of old address space, will there be a market in clean-up services such as the above. give them your newly-acquired address space for two months before you need to use it, and they will test and scrub and write and beg and whine on nanog? it could be that one or two reputable clean-up folk could develop history with the various blockers and be able to get the job done better than we could do it ourselves. randy