IT WORKS!!!!

As soon as I added the SPF records for the domains GMAIL NEVER REJECTS MY EMAILS !!!! I even tested it specifically! Domain with no SPF, rejected. Added SPF, and immediately e-mails were received by Gmail!

This is the TXT DNS I had to add:

Code:
v=spf1 a mx ip4:212.199.167.172 ~all