It could be something like - advanced search. Have a nice ajaxy interface to click some rules together in order to search across your entire email account.
A search icon linked to the search page could be placed between the "New message" and "Mark messages" buttons.
The beginning of the search page should contain the ajaxy search parameter interface and the search results should be listed in a container below it. So if the user wants to change a single parameter he doesn't have to start a new search.
In the spirit of ajax, it could be like Apple's Mail.App. Click an 'advanced' link (small icon?) next to the search form that expands a div below it. In that div are click boxes to choose the search parameters. Check out mail.app to see how it looks there.
Cor _______________________________________________ List info: http://lists.roundcube.net/dev/