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 :
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.