I was notified of user side deletion of more than 50 emails by my provider on March 1st. I was asked to look into it but didn't think nothing of it since I did not notice any lost emails. I use IMAP to fetch my email with Mail on Mac and iPhone. Today I was looking for an email in my "sent" folder and noticed that the oldest email in there is from February 23rd. I'm shocked. My account is not compromised. I have no clue what could've caused the deletion of those emails. I'm on the fence of stopping to use Apple Mail. The only explanation I have which was pointed out as a possibility by my provider is a failed update of external email software in this case Apple Mail which of course would be unacceptable. In all my years of using Thunderbird on Linux this has never happened to me.
From Comment (below) the provider notified me that it detected deletion of more than 50 emails and asked me to make sure it hadn't happened by mistake. I cannot post the text as it is in German. I wouldn't say I have lots of large attachments. Also my iCloud is far from being maxed out
Mail > Mailbox > Rebuild
that should clean things up and might (depending on what is going on) fix any issues with Sent Mail that might be causing messages to go missing.