Have you created a send connector to send emails to the external Gmail recipients?
From your description it seems to be an intermitted issue.
Do the affected mailboxes have the exact same SMTP addresses both in Exchange Online and Gmail?
Please post a screenshot of the complete message trace events of the delivered message.
(Don't forget to hide your personal information)
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.