Google Voice has the same problem. The search function is useless. It does not return results that should match, and it does return results that shouldn't. Scrolling back through just a few months worth of messages can take 10-20 minutes. I wish I knew why it was so awful.
No, I am referring to Google's SMS platform. It interfaces to nearly all other carriers, and is accessible through the "Voice" app or the web page at https://voice.google.com
Tell Voice to send your messages to email, and they'll be searchable from there. Use a query to ensure that you're searching text messages from Voice based on from address or subject. It won't help with searching messages that you've sent, unfortunately, not will it help with messages from before you turned the option on; I've had it on forever as I used to use it for desktop notifications.
