I've tried the default one, hangouts, and then a random one I downloaded and all of them seemed to have the problem. It's only happened with a few people, but they are also the ones I text the most, they are all on AT&T iPhones I think.
If I clear all the data from the messaging app and then delete the messages it seems to fix it for a while, but it gets annoying to do that multiple times a day.