Those blacklists are not Domain name based but IP based. Most likely this has happened cause your ISP has been having badly configure E-mail server (Open proxy). Spammers are notoriously active on misusing those proxies and one important way to limit spam is to eliminate it based on source address.
So complain to your ISP .. they soudl fix they systems and get of blacklist.
http://somequicknotes.blogspot.com/index.html