You can request your current host to have the IP address removed from the blacklist, and to move your server IP to a different address.
Most blacklisted IP's can also be petitioned through the blacklister to be removed from the list, even by someone that is not the host, or you
can ask the host to petition that it be removed.
Also, you can keep track and monitor that best with MX Toolbox at: http://mxtoolbox.com/SuperTool.aspx
There are only a handful of 'good hosts' left that can handle large email sends, it's not an easy task these days...