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

Thank you for the above SMTP2GO idea.  Unfortunately, I"ve just learned that their service does not allow any boxes to be auto-forwarded.  They block all those message.  There are millions of legitimate reasons why one of our mail clients would want to setup auto-forwarding from one box to somewhere else, for convenience.  They are not an option,  and I've wasted a week trying to figure out why email was not being delivered for these boxes.

Does anyone have experience with an smtp relay that allows this very basic email functionality?

Regards,

Stephen

Automatic forwarding to third party email systems (for example: GMAIL...) is a BAD PRACTICE.

It can lead to blacklisting your server's IPs and/or other problems... And that's why many SMTP services prohibit it.

If you can, teach your users to limit automatic forwarding as much as possible, if not to stop doing it altogether...

Gabriele,  Thanks for the message,  unfortunately, that is not realistic.

I'm still interested in anyone that might have alternatives to SMTP2GO.

Many thanks,

Stephen

Hey Stephen, 

Instead of having your users forward emails from one inbox to another, I recommend connecting via IMAP or POP. For Gmail please take a look at this article. 
https://support.google.com/mail/answer/21289?sjid=17034928347308859685-NC

I hope this helps. 

Kind Regards, 

Zach,  thank for this message also,  but as I said, it is not realistic to ask users of email to not forward their boxes sometimes.  If that is what SmarterTools thinks is realistic for your users, then you are certainly not paying attention.  Offices and companies forward boxes all the time, and for very legitimate reasons.

If this is not the case, then why does SmarterMail offer the option to forward boxes???

Stephen

Forwarding mail internally is fine, happens a lot.
That doesn't change the fact it's a poor solution, and forwarding to external hosts is very bad as mentioned. It is VERY realistic to talk to users about not forwarding and moving to a better solution.

Especially in the context that forwarding spam will cause their accounts to not be able to forward at all.

Stephen, blindly forwarding emails from one service to another has been a discussion here in the forums for probably 10+ years. Yes, forwarding emails is legitimate, but then you are likely forwarding all of the spam and other junk along with it. That is what creates problems. If you look back through the forums people here have tried to block clients blindly sending everything to gmail, to AOL, to hotmail and others - because they are also forwarding all of the spam with it. So if a client is sending all of their email from you over to gmail, gmail gets it and then see the amount of spam sent and then just blacklists your IP address.

It is up to you to train and teach your clients why it is a bad idea and to help them develop good practices to protect your server.  They ware using your services, much like gmail, you set the rules of using your servers.

Besides. There is another problem with blindly forwarding an entire inbox off to something like gmail or wherever - which is account ownership.  If a person as part of a clients email domain starts sending all of their info off to their personal gmail (aol, hotmail) account, but the account is in the name of the person, not the domain client, then the domain client no longer has ownership over the data in the mailbox.  If a staffer is forward everything to another service, and they are terminated from employment, then your client may have to go to court to get their email back from the staffer.

What Zach had brought up above is not "forwarding" but instead "gathering"  Meaning AFTER it has gone through spam filters, you reach into a mailbox and extract the email to another location. This way you can synchronize multiple mailboxes to a single mailbox.

And to answer your original question about IP and VM's.  Whatever service provider you use for hosting, regardless if it is VM or physical machines, is going to have a block of IPs available. Some or many may have been previously used and used for spam. Those mail carriers (gmail, yahoo, etc) will have that memorized.  It takes some time to build "reputation", especially if that IP or something in the block was previously used by a spammer. And the spammers LOVE VM environments.  

We ran into a similar situation when we first converted to a VM about 10 years ago.  For the first month or so, it seemed like random stuff was getting sent to spam folders. I had to contact a number of clients (phone calls), tell them to look in their spam folders, just in case, and ask them to deliberately mark it as "not spam" - this also gave me a good excuse to get them on the phone for a few minutes and catch up, see how they are and if they needed anything.

One of the facilities we used for hosting. Their virtual environment had a totally separate block of IPs from their bare metal hosting area. In fact the VM hosting was contracted out to a different company, that is likely why they had different IP blocks.

So the bottom line is that building the reputation takes time. You might be able to accelerate it by making multiple email accounts on gmail and others and then sending yourself email and responding back and forth. Send some large file attachements and making sure you use key words that spammers use like "invoice" and different things and see if any of those get flagged as spam. and if they do, then mark it as not spam and respond to it. "Thank you ! Was waiting for this !"  or something like that.

The more legitimate traffic those services sees from your IP address the better delivery will get.