Look into SMTP2GO as an outbound gateway provider. That's what we use for certain domains and for some of our more transactional stuff that we need guaranteed delivery on.  Been with them for several years without issue.

For your situation, it'd probably be the simplest, and most cost-effective solution.  You still handle your inbound - they just smart host the outbound.

The best way to avoid these types of issues is to "prime" the IP ahead of time by incorporating it into your SPF and other results ahead of it's official rollout as that gives providers time to get those records into their caches and thereby associate it with your domain/organization. That isn't always possible though as you've seen so in that case: 

1. Make sure you have SPF published, DKIM and DMARC for any domains that use that IP, etc. These will go a long way in assuring third party providers that your usage of the IP is legitimate. 

2. Send messages to test accounts you have on Gmail, Yahoo, etc and hit the Not Spam/Not Junk button on it a few times. This helps prime the internal block lists they use. 

3. If all else fails, relaying your outgoing email through a known good relay service as J. LaDow pointed out should get you going in the right direction sooner rather than later.