Can't find registered Python addon inside Blender 2.91.2 (tutorial example)
Actually in the tutorial you have mentioned above, it's 'Operator Search' not 'Menu Search' which you opened but may not noticed. So to have a correct result, you need to enable 'Developer Extras' first.

Then you will get 'Operator Search' in Edit Menu.

With 'Operator Search', you can find your first addon.