FWIW: Attached are screenshots showing the Search menu
that I use, in menu-bar+.el.

The only thing in the screenshots that isn't vanilla
is submenu Search > Icicles.  The rest is all vanilla.
There are 5 submenus (besides Icicles).

You can see how I deal with forward & backward, with
with incremental & nonincremental, and with repeated
nonincremental (forward & backward).  I think it's
pretty clear for users.

(I used to have nonincremental items at top level,
but moved them to a submenu because their use is
less common now.  Admittedly, if someone uses this a
lot then accessing via submenu is less efficient.)

__________
Search
  Incremental Search >
  Nonincremental Search >
  Replace >
  Xref >
  Tags >
__________
Files Regexp (`grep')...
This Buffer Regexp...
Buffers Regexp...
Buffers Regexp for Bufname Regexp...
__________

The last 3 items are for `occur', `multi-occur',
and `multi-occur-in-matching-buffers'.