I've run into this problem multiple times over the past decade.
Each time, I've tried everything I could think of to fix it. In the end, I've always ended up backing up my texts, uninstalling Messages, and then experiencing the pains that
@memyselfandi referenced earlier. I usually watch a movie while re-archiving everything (swipe-swipe-swipe-swipe...)
Every time this happens, I search around, find posts like this one, get my hopes up, and nothing works.
Who knows? Maybe this time will be different. But I'm not optimistic.
One correction / update to what
@memyselfandi shared: you CAN search by unread. Just click the search (magnifying glass), then tap "Unread".