I ran a search on my messages including
I also tried
however I am still getting starred messages in my search results
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.
Labels appears to work better with conversations, so I am going to go with that.