Gmail says "Google could not verify" message on my emails

Hello,

When I send email to my gmail account it says "Google could not verify that example.com has sent this message".

This is really unprofessional for a business email. How do I fix it?

Thanks,

Ben