Gmail Rejected Because Of SPF

If you receive a similar bounce back message (that mentions SPF and authentication issues) when sending to one of Gmail or any other accounts:

then check if the SPF record is configured and configured correctly for your domain. You can check it in MX Toolbox - enter your domain and click SPF record lookup. If the request returns no record or a red record - then either configure an SPF record for your domain or fix its syntax (MX Toolbox will list the issues with it).