I would rather clean up the search dialog than adding yet another menu item. 

I'm currently working on the search dialog, to close bug #355166 and perhaps a few others. I have already replaced some deprecated GtkCombo by GtkComboBoxEntry, I will do it for all.

I think we can add a menu especially because it's easy to do.

But I find the search dialog too complex too. It will be probably better to merge search target and search expression tab and move the settings tabs in Anjuta plugins preferences menu. It's important to keep this dialog as small as possible. It should be possible to use a bit strange widgets: like in the Save As standard Gtk dialog which can be expanded or replace the search button by a combo button (you can click on a small arrow on the right to select another action).

Anyway, I don't plan to make any of these important changes, just fixing a few details.

The more I think about it, the more a like the idea of a new menu item because I really use that one quite often!

Replace all is now part of inline search&replace. That should be easy enough to access.