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. 

Both of you, thanks for your advice.  We have VERY low mail volume with our clients, so this outside SMTP services are going to be only a few dollars each month.  Can you tell me what the DISadvantages to going this route are?  It seems to good to be true.

Stephen

The main disadvantages are that they could block your service in any of these cases:

1 - you exceed the maximum limit of emails provided for by the contract

2 - one of your users mistakenly sends some emails that are detected as SPAM

3 - one of your users sends some emails that are detected as malicious (virus or other)

4 - someone around the world reports the emails of one of your users as spammer

5 - you do not perfectly respect the policies provided for by the contract (read it carefully!)

6 - maybe other cases too...

To me (with another provider, but they are all similar...) both case 2 and case 4 happened.

Of course they can warn you (you have to tell them who to contact and how in case of warnings) and you can then fix it and have the service reactivated, but if it happens you waste a bit of time.

For the rest, I would say that there are no other major disadvantages

It sounds like a non-problem stirred up by the UCEPROTET* blacklists.

The list are discredited and should be ignored.   You will only be dinged for the IPs of your server farm, and it sounds like they have good  control