Just a couple of questions spring to mind.
You say contacts, so are the muted messages just from people you know or all of the messages, even one off messages from someone you only talked to once?
What app are you using for these messages?
When it happened before, we're assuming it was the same app, is this correct?
Do new messages come in muted? So they just show up but you do not receive any notification of the message until you check your app?
Have you checked your DND settings? DND can be scheduled and it can filter who may get through... I believe Bixby has some similar functionality so you may want to check it also.
Thinking back to the previous time this happened, what feels right about how you fixed it? You went to a page where all of your contacts were listed and checked or unchecked something that released them all. You went to a page that was more like settings and you checked or unchecked something that felt like an option?
Do phone calls still work? I know this sounds odd but I can't tell you the last time I talked on my phone or to whom so yeah, do calls still work?