There is no randomness, this is how DMARC works. You need SPF or DKIM alignment (either one will do). Basically what is happening, is that Gmail is slowly enfo

There is no randomness, this is how DMARC works. You need SPF or DKIM alignment (either one will do). Basically what is happening, is that Gmail is slowly enforcing DMARC for new domains. This is a good thing, any domain that sends email should use DMARC, and all email should be properly signed with a DKIM signature. Adopting DMARC can be difficult for existing domains, but if implemented from day one (what Google is mandating here for 'new' domains) it is fairly trivial. That all said: if one is setting up email for any domain, you should focus on DKIM, rather than SPF. SPF is horribly flawed in many ways, and can break in many ways. If you ensure that all your email is DKIM signed (and aligned), you'll have covered 99% of deliverabilty. You should still enable SPF though to support the 1% of legacy email services that don't support DKIM, but just don't rely on SPF alone.