The search I have the most trouble with is searching for things that match a label and are in my inbox. GMail will consistently miss messages. I don't know what it is about them, but I imagine it's some indexing bug. I can go to my inbox, click through the first several pages of messages, and see that a message is there, and has my label. I can go to my label, and find it there too. But a search for 'label:foo in:inbox' will come up empty.