Hi @Safak,
Did you mean you enabled DKIM in Exchange Online?
If yes, do the messages go to external recipients directly from Exchange Online? (on-premises to online to external, no other third-party gateways)
If yes, does this issue only occur to certain recipients?
Please also post the DKIM-Signature part of the message header.
(Don't forget to hide your personal information) Example:
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=contoso.com; s=selector1-contoso-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=KEs42OsNdsrmiPfcVLwpIUZVT+vEuqqygMUN9vA+M2Y=; b=O8/rYT/jYym6TfYubf7UAvHIgqxqbd/RYnWn3KNV9Vc2yLrOOwEUtizwh1pwylLxJYIUKOdkrIEG7DOgqLG+xWLbURRsOTvt24yb1SlHBdTzzUcPHHVNaLFMWtGd3odEuGdjVXBmLdWsyR0s+8PUvqvqINoKrEqBAJm4VRts5ykZtD9RgcKndhQ0aWcWUTIbqagmFWmWkzDlvtW50T82C+KpLIW/SAPtzV/Vkss33HXqEOs05op/Xkca6IeJW1L5uNpv1jNceqnShZt8hIUWP5cjhYfwc9erFnjRjYQIndWVQ0wdoVpLN8GcCRp+Q92VgD09SZJwMuJlRI9kJo9kPw==
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.