Can a new IP address have a publicly bad spam reputation?
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.
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