Update: it seems that adding a dmarc DNS record to the outgoing domains helps. Mails are then not delivered in the spam folder anymore? Does this make any sense?

Hello, 

Yes, adding DKIM and SPF entries for your hosted domains not only ensures that they are delivered more successfully to external servers but also can prevent spoofing that may be attempted by third-parties to impersonate your domains from an external source.

Check out the sources below for some reading material about this.
https://portal.smartertools.com/community/a775/spf-record-how-to.aspx

Let us know if you see some success setting this up on your domains.

EDIT: This is also a very helpful website to utilize for a variety of domain tools. Among them is a tool for SPF that you'll find helpful.

Thank you Matt for your help. Yes, I know about mxtoolbox.com since years and often use it.

Should I add DKIM as well? it seems SPF and DMARC do the job pretty well already, no DKIM really needed.
I am not sure if Smartermail 5.5 supports DKIM? I think it doesn't? Correct? And it has to be set at each domain, not only at the Smartermail forwarding gateway (which runs v 15 free edition with 1 domain).

Robert,

I don't think DKIM was added to SmarterMail until v8 or later. So SmarterMail v5.5 definitely would not have this functionality.

Google and Yahoo both require SPF and to a lesser extent DMARC but they certainly don't require DKIM. Although for an extra added layer of delivery assurance you might want to set a DKIM policy in DNS for _domainkey.yourdomain.tld TXT "o=~; r=postmaster@yourdomain.tld" (basically this is the loosest DKIM policy which says some mail might be signed but don't hard-fail us if it isn't signed).

As long as you have SPF & DMARC then emails should be delivered to Google & Yahoo successfully so long as they aren't forwarded from another source with a DMARC policy. At that point, the only thing that would get your emails thrown into Junk E-Mail would be the content of your emails triggering their Anti-Spam Content Filters (which are admittedly super-sensitive the past couple of months).

One other thing that can help in these cases where SPF/DKIM/etc have already been implemented, is as follows:

1. Create a variety of test accounts on Gmail, Yahoo, Outlook, etc. 

2. Send email to these test accounts from domains on your server.

3. Log in to each test account, navigate to Spam folder and click Not Spam for the received messages.

I have seen this work in a variety of scenarios, and believe it is due to these providers maintaining their own block lists internally. Hope that helps!

Thank you everyone for your help. It is very appreciated.