Outgoing mails get marked as spam

[MKAZE]

We are using Office365 and our whole mail communication is handled via Exchange. For months we are facing the problem of our outgoing mails being marked as spam. 

I can't exactly tell how much of an impact this has, but even just 1% of mails being affected could do harm in a business case. I'm not too familiar with DNS settings, but I just want to verify they are done correctly and maybe someone can help me with that.

Incoming mails are being handled by Baracuda Mail Gateway.

Microsoft 365 Admin is warning about invalid entries in the MX records...

TXT: v=spf1 mx include:spf.protection.outlook.com a:DOMAIN.de -all

MX: dXXXXX.a.ess.de.barracudanetworks.com

MX: dXXXXX.b.ess.de.barracudanetworks.com

Microsoft 365 Admin is suggesting:

MX: DOMAIN-de.mail.protection.outlook.com
 

Might this be related to our DNS settings being poorly adapted by our IT agency?

Is there anything else that comes to your mind that could cause these problems?

[#2]

Hi @MKAZE 

Configure DKIM and DMARC with SPF will raise your trust level so check them in below .

https://mxtoolbox.com/DMARC.aspx

additionally, you can post the message header to check why the message is being marked as spam.

If I have answered your question, please mark your post as Solved

If you like my response, please give it a Like 

Appreciate your Kudos! Proud to contribute! :)

[#3]

Hi @MKAZE 

Try to get an Email (with full headers) that was marked as Spam by one of your customers.

Then use Message Header Analyzer https://mha.azurewebsites.net/ 
Check the Authentication-Results

Enable DKIM and DMARC is also suggested

Regards

Andres