After that we started to get a lot of users in the cloud, we started to move the MX records to target directly the cloud and then transfer to on-premise environment if the user was not yet migrated.

As soon as we started this task, non migrated users started to complains about receiving a lot of spam in their inbox…

Email headers are showing  that the email is well identified as spam, you can see it thanks to the line below :

X-Forefront-Antispam-Report: CIP:;CTRY:;IPV:NLI;EFV:NLI;SFV:SPM;SFS:(2990300002)(438002)(199003)(189002)(19618635001)(4590100002)(450100001)(23846002)(77156002)(110146008)(18206015028)(15975445007)(62966003)(118296001)(64706001)(19617315012)(2351001)(87836001)(229853001)(46102003)(54356999)(50466002)(50986999)(23676002)(106466001)(551544002)(86362001)(42186005)(92566002)(4001450100002)(19580395003)(5002240100001)(5002050100002)(5820100001)(5001960100002)(189998001)(2160300002)(4001540100001)(5001830100001)(5001860100001)(81156007)(110136002)(107886002)(5210400004);DIR:INB;SFP:;SCL:5;SRVR:server;H:eukwrgnut.postexchange.party;FPR:;SPF:Pass;PTR:eukwrgnut.postexchange.party;A:1;MX:1;LANG:en

The thing is that your on-premise Exchange do not take a look at this line and as O365 and your on-premise are not in the same organization, the message is not moved…

To correct MS advise to create a transport rule (https://technet.microsoft.com/en-us/library/jj837173(v=exchg.150).aspx) that check the header of each emails to see if he find the value “SFV:SPM” and then increment the SCL value above the SclJunkThreshold value set on-premise.

Be sure that the SCL value that you set in the transport rule is above (equal is not sufficient unlike what is wrote in the technet page) the SCLJunkThreshold one.