While I agree Gmail search can be infuriating, how do you know it's a complexity issue that keeps it this way?
I don't know if it is accurate, but http://news.ycombinator.com/item?id=850938 sheds a lot of light on why search might be the way it is.
I somewhat disagree. There are some things, most likely due to technical complexity and cost/effort, that google provides at a low level of quality. ie. gmail search!!