I have this exact same problem.
It started several months ago. I found that deleting the messages keep saying pending (even though they have really sent) and resetting over and over works eventually, but that is way too much trouble.
Indeed it only happens with my most common SMS contact which I have probably millions of saved texts with.
I would really like a solution to this. If a solution is posted, could you please email me at link7037+tmo@gmail.com thanks.