But an SMS app is just a front-end - the message database is the same whatever ap you use. I'm not saying that might not fix it, but there's no reason why it should make a difference (because you'd be reloading the database with the same content).
Just to be sure, "Android Messages" or "Android Messenger" is the Google "Messages" app, or something different? There are so many SMS apps, or other message apps that can also do SMS, that it's best to be certain. You could try clearing the app's cache, or even uninstalling and reinstalling it: SMS are stored separately from the particular app, so this won't lose any messages (but making sure you have backups is never a bad idea).
I've never met this problem though, and I've changed message app many times, so it's a bit of a puzzle.