Good idea - IMHO. :)
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.
List info: http://lists.roundcube.net/dev/