It really does sound like you have your bases covered. How long after you created your DNS records did you test things. I am wondering if it’s possible that the SPF hadn’t propagated.

While our team works to maintain a clean IP pool it is also possible that a previous droplet assigned that IP got itself blacklisted somewhere. You can check your IP status on various lists here.

The fact that these messages are not flagged as spam by other providers makes me think that Google is flagging your test messages based on their content or the IP is in a google list (though google tends to block SMTP rather than sending mail to spam in these cases from what I’ve seen).