I had the same experience years ago. Checking again today on my GMail account shows that partial string searches (or prefixes) don't work at all, but I don't really notice it because it gives good search suggestions in the popup.
For example, if I search for a partial string, say the first part of my last name, GMail finds no messages. But there are hundreds of messages from my family members with the same last name in my inbox.
Another example: searching for Verizo results in "no messages found", but GMail recommends I search for Verizon and that shows all the messages I expect (at a glance.)
For example, if I search for a partial string, say the first part of my last name, GMail finds no messages. But there are hundreds of messages from my family members with the same last name in my inbox.
Another example: searching for Verizo results in "no messages found", but GMail recommends I search for Verizon and that shows all the messages I expect (at a glance.)