If lack of substring search is bad, how much worse is the fact that it sometimes doesn't even return all the results for a correct query. I use labels a lot, and I often use boolean searches to search for exactly which Venn intersection I need. A search for "in:inbox is:unread -label:Triangle" (without the quotes) in my gmail turns up messages labeled Triangle. I have similar other problems and cannot trust gmail's search.