My Advice: Leave it to the experts
As someone who has set up their own PHPList, GroupMail, and several other products and projects... let me give you one piece of valuable advice.
If you're looking for the "brain damage free" solution go with a 3rd party provider such as "Constant Contact":
http://www.constantcontact.com
I personally have not used them but several of my clients do and LOVE it. For myself, I continue to use GroupMail and PHPList to send out thousands of newsletters but let me tell you... that's after YEARS of struggling and fighting to get it all "dialed in".
First of all... make sure you're CAN-SPAM compliant (assuming you're in the USA).
Second... make sure your IP address is static and has a reverse DNS for the IP.
Third... make sure your mail server is properly configured... and by properly I mean SERIOUSLY properly configured... not just something that sends out email.
Fourth... make sure your ISP knows who you are and what you're doing. Many ISPs have policies build into their TOS to deal with people who send bulk email... even opt-in newsletters. Just because you're CAN-SPAM compliant and have the user's permission doesn't mean your ISP will like you. I'm on a first name basis with most of the tech guys from my ISP.
Fifth... be prepared to fight every little "wanna-be" blacklist in on the internet. Some don't matter... some do. If you end up on them... its sometimes a complete pain to try and get OFF them.
Sixth... clean your email list! Process those bounces. The big guys will ban you quickly if you start sending to too many "bad" email addresses.
Seventh... get signed up with the "big boys" as far as bulk mail and understand how they work.
Eights... I can go on and on... but I think you're getting the idea...
Summary:
If you have a client and he only wants to email 8,000 people... you're probably WAY better off going with someone like Constant Contact (or someone similar) and letting THEM deal with any potential brain damage.
Keep it simple. :-)
Modern major mail services score spamminess based on multiple reputation factors, if available.
If the only factor is your IP and you don't mail often, this might be "the reputation of the /24 my IP is in". If you mail a lot, you might get your own reputation.
The easiest way to get reputation which "drowns out" the IP reputation of your netblock is to set up DKIM. Send your mails signed. This will establish a per-domain reputation, instead of per-IP reputation, and provides more signal to the automated scoring systems.
The more you work to help the recipients of your email figure out who you are and how trustworthy you are, the more signals they have to work with and the better a job the automated systems can do in deciding that you're legitimate, unlike whoever else bought a virtual machine in the same netblock, pumped out spam and then left, bills to hosting service unpaid and everyone else's reputation tarnished.
[some years later]: I wrote a blog post a couple of years back, walking through a lot of the steps needed to be able to more reliably send to large mail providers: https://bridge.grumpy-troll.org/2020/07/small-mailserver-bcp/
Best Answer
The only way you will get it off the lists is to contact the Blacklist providers and get them to remove it. Which for some providers is quite straightforward, others not so much.
If this IP was allocated to you by Rackspace recently I would probabley go back to them and get them to give you another IP, rather than having to go to all these providers your self.