Have you cleared the reason for being backlisted? If so you should be able to clear the blacklisting with the blacklist owners.

If you have ADSL, a modem restart may change your IP. For me, on cable I have an almost static IP. It has not changed for two years and the only real way of forcing it to change is to change the MAC address of the connecting device (for me that is the ClearOS WAN). There is a chance that is I completely disconnect for a while (hours or days) that someone wlse woll eventually get my old IP address. In that case I'll get a new one. Not every cable supplier is the same.