Medusa HEAD is unstable yet very usable.
I branched the stable medusa-6-0 to do some unstable GUI and indexer development in HEAD. I committed a rudimentary GUI app for file queries. The menus and toolbar are dummies (and the 'Fewer location options' is broken again). Many of the results pane functions came from gnome-search-tool to provide some basic file interaction.
It is probably too late to add Medusa 6.x support to Nautilus 2.5, but it may be doable if we reconsider the requirements. The problem is fitting complex search into a toolbar, replacing the entire search toolbar code, and disabling navigation to avoid confusing the user. Updating the search view wont be a difficult task; copy and modify the existing list view or try the new pluggin architecture. Simple search and complex search may be turned into dialogs that create a search URI that open a spatial window. While this plan addresses the toolbar and navigation issues, it will introduce another one. If a save search (folder) is opened from the desktop, there is no way to see or edit the search criteria. The msearch-gui app could be used to edit the criteria of a search folder.