Funny you mention it. Search in opera mail is excellent and extremely fast. It searches through all of my 12k mails in the blink of an eye.