I've never had issues with gmail, though I know a few people who did. But I think setting up SPF and DKIM will, for the most part, do the trick to allow communicating with gmail users.

The problem is the other provider. Yahoo, AOL, Microsoft. They're all a pain in the neck and much, much stricter. And sadly, they still amount to a not insignificant portion of the market.