Well, what is there to say. Email is bad, very bad actually. I host some mailing list for group of friends, and all emails were flagged as spam. Normally, this is not a problem since I use mailgun as an external SMTP host. Or that is what I thought, but postfix (the MTA that mailgun uses) did not agree.
I was using a so called: Sender-dependent transports. This works great for just sending emails from an Mailcow domain. I am able to set a specific SMTP host for every domain, and Mailcow uses that domain to send emails from that domain. For mailing lists it is bit different (called aliases in mailcow). When somebody sends email to a mailing lists, the mail-server hosting that mailing list will forward it, but forward based on the sending domain. And now the problem is in the name. Mailcow (or postfix for that matter) uses the sending domain to route outgoing email to the proper SMTP host. And remember, the sending domain is not the Mailcow domain, but the original domain that the original sender uses!
When Mailcow cannot find a entry in Sender-dependent transports map, it will use the default outgoing SMTP host, which is by default the one of the Mailcow instance itself. In my case, this is some sketchy VPS ip address that probably somebody has used to send millions of emails concerning some the Arabic sjeik that has billions of dollars for you.
Now, fixing is easy. To fix it I created an mailbox called everbody@example.com, and use the forwarding function in SOGo. And since SOGo always uses the specified SMTP host, all mail will be send using that SMTP server, and the problem is fixed!