It appears that Google has increased requirements for email delivery, particularly with SPF settings. Emails are being rejected from domains that do not have SPF records or violate SPF.
We recommend checking your SPF and ensuring your settings are correct in order to improve mail delivery.
For further information on SPF please see our articles:
Read our Knowledge Base article on Email Authentication and Phishing Protection - An Explanation and Exploration
Read our Knowledge Base article on Implementing SPF for the MailRoute Outbound/SmartHost Service