I have spent many days debugging the issue, to no avail. Every other operator accepts my email, and my domain was never used to send out spam (I set up DMARC to make sure I am aware of all outgoing email). I imagine the IP might have been the issue, but I cycled through a few hosts without success.
Everything was configured correctly AFAICT, I could send email to all major providers, except microsoft. SPF, DKIM, DMARC were all set up. I tried many different configuration testers, and they all returned green on my domain.
Since migrating to fastmail (keeping the same domain), I haven't had any problem.
The thing is, I agree with you, the world would be a better place if everyone could host their own email. But at the end of the day, I need the ability to contact users using the major email providers, and so do I suspect many HN users.
I'm running an email server for myself since 1998 and in addition some low traffic email servers for a few small companies that I administrate and we have had no delivery problems so far, not even with Google, although I have heard from other people that run their own email servers, that Google occasionally puts delivered emails in the Spam folder.
I always keep an eye if some of our IPs may appear on any of the well known abuse lists, but so far that never has happened. I would guess if once there's coming spam from your mail server IP, it is negatively branded forever.
The thing with gmail is that this is true even even for legitimate email from long-known connections when the path is gmail to gmail!
Even worse, it can be true within a gmail-hosted corporate space, so email from your boss ends up in spam!
So it's nothing specific to whether you host it or not, it's just a reflection on gmail's spam false positive rate being particularly bad.
Start with a good IP address (static, not residential ISP, not on any block list). Search for sites that will help check this. https://mxtoolbox.com/ has many useful bits but there are others, try them all. Set up DNS correctly, forward and reverse.
Set up postfix. Tons of guides out there, here's just one list: https://www.linode.com/docs/guides/email/postfix/ Read the various guides but most importantly read the postfix documentation in detail. It is very good and has everything you need to know. Configure postfix to enforce all sanity checks that it supports during the delivery connection phase. This alone will cut off nearly all spam!
Install a local MUA (mutt would be my favorite) and you're up and running and should be able to send and receive, so test that thoroughly. Probably ending up in spam at this stage but should work. Mark it not spam in recipient. Note that if you had to register a new domain name, it'll likely be penalized as too new for a good while.
Set up a cert (Lets Encrypt) for postfix.
Configure SPF correctly. Read online guides but also read the RFC. Again, use online tools to validate your work. SPF is great.
DMARC, DKIM are more controversial and less clear-cut useful than SPF. Read about them. I do set these as well. Set the notification email so you get reports (which aren't that useful but still). Use the online tools to validate.
Set up Dovecot to enable IMAP.
If all we had was a few giant corporations with proprietary apps and proprietary protocols, that's not the Internet.
As I post every time on these email discussions, the difficulty of running your own email infrastructure is vastly overstated on HN. The more people do it, the better off the Internet world is for all of us.