Can a new IP address have a publicly bad spam reputation?

Symptoms

If you add a new IP address to your server and send an email from the new IP, you may find that your emails will not arrive at their destination.

Description 

If you are sending an email from a new IP address, and you find that you can't send emails from it, it's possible the IP address itself has a bad spam reputation.

Since a lot of emails go through the big Email providers (Gmail, Yahoo!, Hotmail), it is usually not possible to see why they block your email. The only notice you would get would be in the bounce-back message of the email.

However, and this is rare, the IP address you are sending from itself has a bad spam reputation. And the reputation is known publicly. 

To check if your IP address has a bad public reputation, you can use the following third-party URLs. They can show some reasons for the IP address being listed in public blacklist pages:

Example sending IP: 111.222.333.444  <-- not a valid IP

Third-party URLs to check reputation:

https://www.spamhaus.org/query/ip/111.222.333.444
http://matrix.spfbl.net/111.222.333.444
https://www.abuseat.org/lookup.cgi?ip=111.222.333.444
https://ipcheck.proofpoint.com/?ip=111.222.333.444

Replace the IP above in the URL with the mail server sending IP address you want to check.

For more examples, visit here: How do I check if my mail server is blacklisted?

Workaround

If an IP address is known publicly to have a bad reputation, we would recommend getting the IP address replaced with another one. As mentioned, this is rare but can be found on some occasions.