Hi,
I think the Messaging history is linked to the call history - I just double checked that by typing the first 2 digits of a number I only ever call but never text to (it's a landline).
So you'd have to go to the Phone app, Call history, and search for the numbers you want to delete, then remove from the call history. Kind of tedious, but I can't think of a better solution...