I ran a search on my messages including
I also tried
however I am still getting starred messages in my search results
Web Applications Stack Exchange is a question and answer site for power users of web applications. It only takes a minute to sign up.Sign up to join this community
Those conversations are coming up because stars are applied to individual messages, not conversations. So, at least one message in the conversation lacks the star and so meets your
If you star all the messages in that conversation I'll bet the conversation drops out of your search results.
Labels work in much the same way, which is why it can be problematic to search for negative criteria.