I've been dealing with this issue quite often with SMS. I've done OATH reset, reintegration of Twilio, deleted contacts, new contacts, deleted conversations ...
What works to get this to work consistently? It was working fine until I decided to delete a conversation with a test contact, to restart it from scratch.
I'd appreciate some help as it's taken hours of my time.