I would think that requesting OAuth verification for the Apps Script project before publishing a new add-on,
would be the way to go.
I haven't successfully published a new add-on listing recently, so I'm not sure if things have changed.
They should have seen the custom menu even if they didn't see an add-on menu.
If they didn't see a custom menu, then probably what is happening, is that there is a fatal error when your code is parsed by JavaScript, even before anything runs. So, you can get a JavaScript error before any code even runs.
So, what happens is, that your code to build the menu never runs because there's an error before it can even run.
That can happen during the process when your code is being evaluated by JavaScript.
That's the "classic" issue for a menu not appearing for an add-on.
Now the question is, why did the error happen?
It could be an issue with a global variable.
Or the order of your files.
Are you using V8? See your manifest appsscript.json file.