Mail app won't send emails to anybody with a gmail address

We are using an email server through our website provider.  It's set up in the Microsoft Mail app, and generally works with no problems.  But we've found that every time we try to send an email to someone with a gmail address, it gets returned with the following error:

    SMTP error from remote mail server after end of data:

    550-5.7.1 [104.245.16.215] Messages missing a valid messageId header are not

    550 5.7.1 accepted. n5-20020a17090a2fc500b0022c2f9ab15esi2524588pjm.5 - gsmtp

Any ideas what's causing this and how to fix it?

We thought maybe it was our email provider, but we tried going to the email website, and sent an email to a gmail address, and it worked fine.