i have been experiencing this problem ever since upgrading - when i put in a word/name to search all my messages, the only results are when the word/name is in the text of the message.
a couple of months ago, i called apple and the only suggestion was to delete all my messages without restoring them - basically to start fresh. the suggestion was based on the possibility that there was a problem with my message data. with 4+ years of text messages, i didn't see that as an option and have been limping along whenever i need to find the messages i sent to someone i haven't messaged in a while.
anyone have a real solution?