The search is not unusable, I use it every day. It could be better though, and I get the feeling it could plan the query more efficiently too. I think it needs a better query syntax for those hard to find e-mails.