Menu randomly does not display
Last time I encountered such thing, it was on Drupal 8. The culprit was caching. In a gist, if the page was viewed by a user who doesn't have access to that menu and that result gets cached, the page will be served from cache (without that menu) until the cache is cleared. Might want to disable page caching, then block caching, in admin to verify this. If you have any other caching mechanisms, try disabling those too. A good indicator that this may be the case is the fact that you need to clear an external cache for one of your setups.

Another culprit would be template-side logic (template.php or directly on the templates themselves). Since you're using D7, it's relatively easy to sneak in PHP into templates. You might want to review your templates for this.

Lastly... there's JS and CSS. You might want to do a View Source to see if the markup is actually there, but just removed by JS or hidden by CSS. Due to Drupal's steep learning curve, it's very tempting to just do everything in JS and CSS. Also, if the menu is dynamically generated or enhanced by a script, a broken script might have interfered with that generation/enhancement.