This is my experience too with a private server, but I did need SPF, DKIM and Dmarc. These 3 things do require some expertise, but running a mail server already requires that. So it just needs extra time :)
More than just SPF, DKIM and DMARC; mails still get silently discarded if you come from an IP address with a poor reputation. For this reason most of the large VM hosting providers will work but not give great results.
