You or someone else get a new phone and forget to sign-out of Messages and iCloud before getting rid of old phone?
Other thing to try: if reusing an old message thread, delete it (might have old device address embedded in it). Seem to recall someone also got stuff unstuck by tapping on an old bubble of the thread and or go through edit motions on the thread.
These two are the usual culprits for messaging problems.
Otherwise, pretty much working for majority of people, me included (remembered to exit out of Messages and iCloud before new phone and don't keep old threads lying around on the phone).