How Google and Microsoft have made e-mail unreliable
penguindreams.org
penguindreams.org
The problem with Google and many other mail software(!) is, that they don't /really/ care about DKIM (and other new shiny stuff nobody gives a f* about) and have spam filters they trust 100%: like subnet rating - that should be changed indeed!
Maybe larger servers use the age of your domain registration as a factor. I've had mine for quite a few years now.
I am no email server expert but it sounds like he needs to Google SPF, Reverse DNS and Domain Keys.