I was at a lost when this happened to me as well....until I did this...

1. Go to a the particular person in "Contacts" and bring up their screen
2. Tap on their name (at the top)
3. Tap "Link more profiles..."
4. Link them to another contact (only temporary)
5. Close contact
6. Open that person's contact again
7. Tap on their name or their link...and tap "unlink"

That person and their conversation will reappear in your "Messaging"...where you can individually delete conversations one by one or the entire conversation.

Do this for each person that no long shows up in your "Messaging" area.

Reply back and let me know how it goes...it should work for you!

Reply