Okay, so after some investigation, I discovered that the Search menu can be redefined.
<menuContribution locationURI="menu:org.eclipse.ui.main.menu?after=Navigate">
<menu
id="org.eclipse.search.menu"
label="Search">
<separator name="dialogGroup"/>
</menu>
</menuContribution>
The one minor disadvantage with this solution is that the menu items in the Search menu are rearranged depending on where the new menu items are added.