This is something very few of us do: You hire a hosting service from a hosting company and even though you take notice of many issues like server specs, support, bandwidth etc., you usually don’t even think about the IP address they assign to your brand new server.

Dedicated server IPs are usually assigned in sets of 5 consecutive IP address like 64.20.56.0, 64.20.56.1, 64.20.56.2, 64.20.56.3, 64.20.56.4. These IP addresses are not created for you, they were serving to other servers/domains before you and they might be abused by their previous owners. This sometimes happen if they belong to a spam/warez/hack related site and before the hosting company terminated their account, they might have used the IPs in unacceptable ways and get blacklisted. And sometimes they belong to legitimate sites but they had security breaches which were abused by hackers and IPs are blemished.

Whatever the reason is, if these IPs which you are going to own now is blacklisted in large email networks you will have troubles sending emails from your sites. Most of your emails might be filtered to spam/junk boxes in frequently used email services like hotmail.com and some other emails might be rejected with a bouncing “you are blacklisted” message.

So it is imperative to make an blacklist check before your dedicated server is assigned IPs and ask your host to change them if the IPs they are going to assign are flawed. There are different sites which you can check IPs blacklist status. Some of them are:
http://whatismyipaddress.com/staticpages/index.php/is-my-ip-address-blacklisted
http://www.mxtoolbox.com/blacklists.aspx
http://www.kloth.net/services/dnsbl.php
http://www.email-unlimited.com/tools/check-ip.aspx

So what you should do BEFORE hiring a dedicated server is to ask your host which IP your server will be assigned and then make a check in the sites above and if the IP is blacklisted, ask for another IP before they build the server.