Iphone texting peculiarity

I just got and began using an iphone 4s. When texting i find that some times the intended recipient claims not to have received the message while the iphone says it was sent. I have noticed that these seem to occur when I stick a new message at the bottom of a previous string of messages. Could this have something to do with the reciepient having deleted those messages it was to be built on and therefore the new message can find no where to land?

If it matters the system is ATT and the other phone is a Pantech ease.

The recipient deleting the previous string of messages won’t matter; the new message will just appear as though a stand alone message.

Is it only happening with one contact?

Yes, only with one contact. And my phone shows that it has been delivered.