Checkout the reunion_medusa branch of nautilus from gnome cvs to see a some functionality already restored. Be warned though, Nautilus will go belly up if you try to close the search-list-view. There are serious issues with the complex search toolbar that must be addressed before this stage can be completed.

The most obvious problem is that the optionboxes don't display the active menuitems. I lost a lot of momentum trying to fix that before a, sinking to despair, and b, realizing fixing the issue wont make complex search usable. Complex search used a hacked version of the GTK+ 1.x hwrapbox from GIMP. GIMP updated it to GTK2 a few months ago, but a lot of refactoring is need to make it work in Nautilus/Medusa. Even is it were pursued, figure 1, illustrated that this does not work in a tool bar. Switching to a hbox as is in the current code and illustrated in figure 2 doesn't work in small windows.

Complex search is better suited in the side bar or in a modless dialog window. Consider gnome-search-tool in figure 3 as an example of how a dialog might behave. I like it's gui and as users are more accustomed to it then the original Medusa complex search, I think it's UI should be emulated when possible. I don't care for creating additional windows because it seperates the query from the results. The side bar would be an excellent choice if the width of the search criteria could be prevented from getting too wide (See figure 4). figure 1: Nautilus complex search tool bar using hwrapbox. figure 2: Nautilus complex search tool bar using hbox. figure 3: gnome-search-tool. figure 4: Nautilus complex search bar proposal.