How to remove an IP address from a blacklist
Determine why you are listed
Each blacklist has their own listing criteria that may include technical listings, policy listings, and evidence based listings. Technical listings are those that occur mostly from mail server configuration issues such as missing or incorrect reverse DNS records, missing on incorrect banner greetings, and mail servers operating in IP address space that an ISP has specified that mail servers should not be operating in. Policy listings are those based on an operator that does not wish to receive email from certain countries, or ISPs, or has a history of no honoring unsubscribe requests. Evidence based listings are those where the operator has receive direct (or indirect) evidence that an IP address has been involved in sending unsolicited emails. You'll need to visit the blacklist's website and perform a lookup on the specific IP address. Most blacklists will provide general listing reasons but will not provide access to the email addresses the spam was sent to.
Resolve the underlying issue(s)
Once you have determined why an IP address has been listed you can begin your internal process of resolve the issue. This is a good time to confirm that your network, mail server, and computers are properly configured. Common resolutions include: fixing forward and reverse DNS records, STMP banners, scanning all machines on the network for viruses, patching operating systems, configuring routers more securely, and enforcing strong passwords.
Follow the blacklist removal process
After you have fixed the issues you'll need to go back to the blacklist's website and follow their specific removal process.
Some blacklists have a self-service removal feature. These generally allow for near immediate removal from the blacklist. Be sure that you've resolved the issue before doing this. When an IP address gets listed again after removal the process can become more difficult.
Time Based Removal
Most blacklists do not offer self-service or manual removal. They have a process that runs that will automatically remove low-level listings within a week or two. If the IP address has been involved in sending spam multiple times or in high volumes this process may take longer.
Things to keep in mind when contacting a blacklist operator
Blacklists are legal in most countries. There is no point in threatening legal action against blacklists. Courts have ruled numerous times that they are legal. The blacklist is not preventing you from sending mail. The operator of the receiving mail server has made a person choice to consult a third party before accepting email from them. When all else fails contact the receiver's mail administrator over the phone to attempt to resolve the deliverability issue.
Don't lie. Don't tell the operator you've resolved the problem when you haven't. If you lie that you've resolved the issue and it happens again they will likely not talk to you any more.
Keep it polite and professional. When you are having difficultly in removing a listing let them know what you are trying to do to resolve the issue. The more professional you are with them the more they'll be willing to help you resolve the issue. They are trying to stop people from receiving spam, not trying to keep you from legitimate non-spam correspondence.