If you really have deleted the search definition, then it can't be adding to the menu. Have you checked to make sure that the search definition has really been deleted?

You may have another search definition that adds to the menu, or the link may actually be generated by the form itself (under form configuration, you can add create and display links to the menu).