Hi,
Please understand that the tag “Exchange Server” is for general questions related to Exchange Server . According to your description, this issue only occurred with Samsung devices, we can consider that this issue is about Samsung devices instead of Exchange Server. I suggest you to contact Samsung support team for further help. Also, it involves Outlook mobile app, you can also go to dedicated forum for Outlook for Mobile for help
And based on my personal experience, maybe you can try to check ABQ List, in EAC click Mobile->Mobile device access, in this interface check if there is any Block/Quarantined setting for Samsung phone, and also, you can create new Mobile device access to allow Samsung device.
Hope this helps!