Solution: Ask Siri to read your unread messages. Siri will read the ones you can't find by scrolling through your conversation list in the app and you can watch the badge count drop with each message read to you.
Thanks to this discussion on Apple's Community.
For months, and across multiple iOS versions, my Messages app was showing 4 unread messages every time I went through and made sure all visibly unread messages were read. Even selecting to filter on unread message only, the app would show that I had no unread messages, but the badge remained.
I tried:
- Scrolling through my entire conversation history until I couldn't scroll anymore.
- Disable the app, power off the phone, reboot, enable the app
- Disabling and re-enabling notifications