Hi Asaf,
Are the sent mails delivered correctly to the recipients?
Does this issue happen to reply emails or all outgoing emails in these users' Outlook?
Please check whether the users have the "When replying to a message that is not in the Inbox, save the reply in the same folder" option enabled under File > Options > Mail > Save messages section.

Regards,
Steve Fan
Please remember to mark the replies as answers if they helped.
If you have feedback for TechNet Subscriber Support, contact
tnmff@microsoft.com.