Above the message list in Thunderbird (15.0a1, latest trunk at least) is a Quick Filter button. When you click it, it drops down a little bar (that stays there unless you click the Quick Filter button again) where you can type in a search field. You do not have to press enter in it. It's find-as-you-type. There are also buttons below the field to control what parts of the messages are searched.
In Opera's built-in mail client, there's a search field above the message list. It's find-as-you-type too. With it, you just type a space-separated list of words and Opera will show the results (You can use quotes for an exact-string search). Opera does this really fast because the entire message is split up into words and indexed into a search database when the message is fetched. So, when you search, it's a simple database lookup. Opera doesn't give you control over what part of the message to search in or to use regexp. If you want that, you have to set up a label and use rules etc.
A cool thing about Opera's search field is that it searches the current view by default, but you can click to search all messages instead of you want.
You can also save the search you as a label with rules in Opera.
Now, even though you weren't looking to sort though, Opera has a lot of ways to sort messages (way too much to go into at one time). It even has a lot of views by default for sorting messages. Chances are, the messages you're looking for might already be sorted into a few.