Sender Policy Framework requires you to add a bit of extra DNS for your domain. I started there. I also set up DKIM at one point. The deliverability to my addresses (some of which are gmail) seems to work fine regardless of which gmail account I use, but other users report that they cannot receive email at their respective gmail addresses.
I would also point out that gmail is perhaps one of the most popular (and probably most-abused) email systems in the world. There's a strong chance that a lot of those orphaned confirmation table records are just script kiddies screwing around. If, however, you are getting complaints from real users about the email never arriving, your emails might be getting caught in gmail's spam filters. Based on my very limited knowledge of google's algorithms, I would NOT be surprised if every account on gmail has its own spam filter rules that are tailored to some degree to that user.
I'd also fully expect that your domain, if it lacks SPF and DKIM or whatever up to this point, might be suffering in some kind of internet limbo where the reputable anti-spam systems consider your email "dodgy" and so you are getting stuffed in the spam folder. It may take you time to climb out of this jail/pit/prison. I'd start by setting up SPF/DKIM and whatever good-citizen-type stuff you can and hopefully your spam factor will improve over time.
