Seems like basic debugging of complex systems to me. Yes, you may never by 100% sure that the lack of a SPF record is the root cause. But you do know that you d

Seems like basic debugging of complex systems to me. Yes, you may never by 100% sure that the lack of a SPF record is the root cause. But you do know that you don't have it, that some of your messages are getting spamfiltered, and it's well-known that Gmail uses it for spam detection. So just add it already. The worst that could happen is that you wasted a few minutes on something that doesn't fix the problem. How much time have you spent messing with this already? I don't know what your history is, but there's piles of bugs that I've had to fix by just trying random things that seem vaguely related to see what happens. If I refused to try anything until I was 100% sure of the root cause, then lots of bugs I've been assigned would never have been fixed, and many more would have taken 10x longer.