normally I would say it's a carrier issue, but since you say you've already been to the carrier... I would suggest submitting an error report to Samsung Members app. This is a little different than vising the store.... because the app will collect the phone's logs (activities) in the process of submitting the report. Reproduce the issue if you are able to, or just submit whenever you see the issue again. it would be best to attach screen recording but if it's difficult then maybe a screenshot will to just fine as well but not necessary.
The stores may not have been much of a help because this is a software related issue most likely and they just don't have the tools or the in-depth professional knowledge to help.
That being said, would you mind sharing your device's model number and the software version? are yo using the Samsung Messages app or another 3rd party messenger?
I have go through everything, didn't solve the problem. Finally, Carrier changed a new SIM card for me, no problems so far.