Often times when people complain about this there is some misconfiguration somewhere, which is admittedly hard to notice a lot of the time. One big gotcha with DKIM, for instance, is that TXT records have a limited size in DNS, so if you have a large key you likely cannot fit it within a single TXT record (an RSA 2048 key is too big, unfortunately). In theory you can split the key in DNS, but I’m not sure if every mail server will handle this correctly. Anyway, people will make an RSA 2048 key (or larger) and try to stuff it into a single TXT record and they might not notice that it doesn’t fit (e.g., their DNS provider’s interface may truncate the record silently). So, it’s good to confirm after the fact that the records are good and working (there’s a number of free services that will do that, e.g., https://www.learndmarc.com/).

The other thing that’s a bigger deal than I think it should be is rDNS. The rDNS on the mail server really needs to be the same as the MX record or certain spam detectors flip out. If your MX record is mail.example.com, it seems like the spam detectors really want the rDNS to be mail.example.com and not example.com, for instance. You’ll see some advice online that suggests that the rDNS record just has to exist and doesn’t have to match exactly, but this has not been my experience.

Beyond that I have also registered for Outlook’s SNDS and Google’s Postmaster services, and I’ve also added myself to the whitelist here: dnswl.org/. I’m not sure how much of difference that makes, but it’s something else you can try.