While email between other self-hosted servers seems to work just fine, Gmail is marking inbound mail as spam. (Once it’s marked as “not spam”, it receives fine, but that’s not good for initial email contact.)
Is there some kind of specific setting necessary for the Microsoft & Google of the world?
Also make sure SPF and DKIM is working properly. You can also register your domains at Postmaster Tools – Google Even though the amount of email might be too little to show anything in there, it also can’t hurt.
I’ve used MXToolBox on both domains I have hosted there and they show that both DKIM and DMARC are valid. One of the two domains is blacklisted on a spam list–probably because the domain name ends in .cc–but the other one is not.
Per your suggestion, I have added both domains to the Postmaster Tools. (Thanks for that.)