Have you also set up reverse DNS and done it all for IPv6 too? The second part was what I was missing a while back. I do agree that Google and Microsoft are extremely strict with what they accept and it's not always easy to tell why you get thrown to the spam pile.