Emails sent with MimeKit / Outlook are falling to gmail's spam folder for the first time

We are using MimeKit as SMTP client for sending emails to our users. Typically, the first time it arrives to their gmail accounts, it falls into the spam box. Then if removed the 'spam' flag, subsequent emails stay in the inbox.

Is there something necessary to do at C# level? or maybe at Outlook/Azure-DNS level?

The C# code snippet is as follows:

            var message = new MimeMessage();
            message.From.Add(new MailboxAddress("Notifier", smtpUser));
            message.To.Add(new MailboxAddress("User", recipient));
            message.Subject = subject;

            var bodyBuilder = new BodyBuilder() { HtmlBody = html, TextBody = text };
            message.Body = bodyBuilder.ToMessageBody();

                using (var client = new SmtpClient())
                {
                    client.ServerCertificateValidationCallback = (s, c, h, e) => true;
                    client.Connect(current.SmtpUrl, current.SmtpPort, SecureSocketOptions.StartTls);
                    client.AuthenticationMechanisms.Remove("XOAUTH2");
                    client.Authenticate(current.SmtpUser, current.SmtpPass);
                    client.Send(message);
                    client.Disconnect(true);
                }

For the first time, gmail is showing it flagged as 'spam':

Pressing 'Looks safe' will make subsequent emails valid, but we need the first one to look safe.

I am attaching also the entire mail content received at gmail:

Received-SPF: pass (google.com: domain of [email protected] designates 2a01:111:f400:fe44::629 as permitted sender) client-ip=2a01:111:f400:fe44::629;
From: Notifier <[email protected]>
To: User <[email protected]>
Subject: Notification
Thread-Topic: Notification
Thread-Index: AQHVYyrMLhjkfFeVAkmoUM8Y198VPw==
Date: Wed, 4 Sep 2019 14:12:34 +0000
Message-ID: <[email protected]>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-messagesentrepresentingtype: 1
x-originating-ip: [13.84.163.72]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 6291f624-e9b1-484f-f114-08d73141eea5
x-microsoft-antispam: BCL:0;PCL:0;RULEID:(2390118)(7020095)(4652040)(7021145)(8989299)(4534185)(7022145)(4603075)(4627221)(201702281549075)(8990200)(7048125)(7024125)(7027125)(7023125)(5600166)(711020)(4605104)(1401327)(2017052603328)(7193020);SRVR:BN6PR1401MB1907;
x-ms-traffictypediagnostic: BN6PR1401MB1907:
x-ms-exchange-purlcount: 1
x-microsoft-antispam-prvs: <BN6PR1401MB1907D7529E3B99DE63CB070DA0B80@BN6PR1401MB1907.namprd14.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:660;
x-forefront-prvs: 0150F3F97D
x-forefront-antispam-report: SFV:NSPM;SFS:(10009020)(4636009)(366004)(136003)(39830400003)(396003)(42606007)(346002)(376002)(199004)(189003)(66946007)(2906002)(3480700005)(558084003)(476003)(316002)(25786009)(486006)(256004)(508600001)(52116002)(99286004)(66556008)(7116003)(66476007)(33656002)(305945005)(71200400001)(71190400001)(66446008)(64756008)(8936002)(6486002)(7736002)(81156014)(81166006)(8676002)(6306002)(51815007)(10126004)(386003)(6506007)(53936002)(66066001)(86362001)(221733001)(9686003)(236005)(6512007)(606006)(14454004)(6916009)(6436002)(186003)(54896002)(26005)(6116002)(102836004)(3846002)(1411001)(5660300002);DIR:OUT;SFP:1101;SCL:1;SRVR:BN6PR1401MB1907;H:BN6PR1401MB2004.namprd14.prod.outlook.com;FPR:;SPF:None;LANG:en;PTR:InfoNoRecords;A:3;MX:1;
received-spf: None (protection.outlook.com: efferenthealth.com does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam-message-info: bHkvE3Co8At1/X9BzBqbqZFNCIBAppNhqQqCJDoMByjqBv9VGO25sOpCKS8OSh1obZBR1t5nvkdn0CFuuFoGjhwNaXt7MakSQfeS8auVa0d/GUpLb7Y3oJ8Xm2az23Z4+l3YP4ITa5Fhd8DxliNV8JO4ZYDxC6uG3Gh8my4MewFPQScRgUgx49un88gu8zK3MDyUhxIlYB1WjdqPPG3xtQMIBHbA4EuPFa5Is2Jk7D4PsMjrpTvL8GyZVYhgVWC71OrwG7C575IB1XIanF7woc0VZxBlAjh1xY8gaUDYuT7Lc1b/cSKcyUjOG7J0XR8ilS4fp86IaGeKdivi4h2MJ8oqW+A9obH2+GW5NTpBMgvYE7zFNBQhxuuC/jxny7F2zs4z5vacC0HOXeUwgfOLWZsUdZC2SDW6HjXkw0TejIA=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_98UUW7B0H8U4EB3P8CQCSUEN2localhostlocaldomain_"
MIME-Version: 1.0
X-OriginatorOrg: efferenthealth.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 6291f624-e9b1-484f-f114-08d73141eea5
X-MS-Exchange-CrossTenant-originalarrivaltime: 04 Sep 2019 14:12:34.9389 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 02ecab7f-85de-4d13-9c86-db5eefd90ee2
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: zj/y6ItrIybuyjEREqOxS6sBThdrcjGbcWxxKICSNnb1h2GZnVz0UsJO0Kcp51LYMrFzeRKKgbFFnJPNgXa2GoLY5CBVrkaMzJbHf0oywnA=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN6PR1401MB1907

--_000_98UUW7B0H8U4EB3P8CQCSUEN2localhostlocaldomain_
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64

VGhlIHVzZXIgQSBib3N0b25tZWRpY2FsZ3JvdXAgZnJvbSBCb3N0b24gTWVkaWNhbCBHcm91cCBo
YXMgc2hhcmVkIHdpdGggeW91IGEgSW1hZ2luZ1N0dWR5IHJlY29yZC4gWW91IGNhbiByZXZpZXcg
c3dvcmQ9YTM4YWEyMWQtMTJhMy04YTQ1LTZjNTEtMzUwZDNjMzY5ZDcwPg0K
--_000_98UUW7B0H8U4EB3P8CQCSUEN2localhostlocaldomain_
Content-Type: text/html; charset="utf-8"
Content-ID: <[email protected]>
Content-Transfer-Encoding: base64

PGh0bWw+DQo8aGVhZD4NCjxtZXRhIGh0dHAtZXF1aXY9IkNvbnRlbnQtVHlwZSIgY29udGVudD0i
dGV4dC9odG1sOyBjaGFyc2V0PXV0Zi04Ij4NCjwvaGVhZD4NCjxib2R5Pg0KVGhlIHVzZXIgQSBi
b3N0b25tZWRpY2FsZ3JvdXAgZnJvbSBCb3N0b24gTWVkaWNhbCBHcm91cCBoYXMgc2hhcmVkIHdp
dGggeW91IGEgSW1hZ2luZ1N0dWR5IHJlY29yZC4gWW91IGNhbiByZXZpZXcgaXQgYnkgY2xpY2tp
bmcgb24gdGhpcyBsaW5rDQo8YSBocmVmPSJodHRwczovL2VmZmVyZW50ZGV2LmF6dXJld2Vic2l0
cmU8L2E+DQo8L2JvZHk+DQo8L2h0bWw+DQo=
--_000_98UUW7B0H8U4EB3P8CQCSUEN2localhostlocaldomain_--

Solution

I have a few thoughts but no definitive answers for you because I don't have inside knowledge of how Google does their spam categorizing.

Avoid using names like "User" and "Notifier" in email addresses. That screams "automated message" to me and Google likely has semantics that weigh that type of naming convention as having a "spam" and/or "fishing" bias.
Try setting the Content-Transfer-Encoding of the text/plain and text/html parts to something other than base64; I might suggest quoted-printable:
```
foreach (var part in message.BodyParts.OfType<TextPart> ())
    part.ContentTransferEncoding = ContentEncoding.QuotedPrintable;
```
This likely isn't an issue, but it's possible, so I'll mention it. Avoid using "@localhost.localdomain" in the Message-Id header. If MimeKit is generating those, it's because it doesn't know what your hostname is and couldn't figure it out, but you can override this behavior by doing this:
```
message.MessageId = MimeUtils.GenerateMessageId ("efferenthealthllc.onmicrosoft.com");
```
Maybe try removing the Content-Id header from the text/html part? Again, I don't see this is likely to be an issue, but it's worth a shot of none of the above changes fix things.
```
foreach (var part in message.BodyParts.OfType<TextPart> ())
    part.ContentId = null;
```