That is the exact problem that got me to abandon my splendidly working, self-hosted email stack. I had so many instances of mail just not getting delivered, despite doing absolutely everything correctly, that I gave up.

Thankfully not a problem we've encountered yet. All my mail is DKIM signed, SPF aligned etc. I also registered on dnswl.org which is a signal quite a few people seem to use.