I met this case sometimes on Homepage. The menu was cached when I return Homepage from another category page.
Does anybody here have idea and solution for that?
The issue is full page cache issue, You can try with your menu block add this content in menu add cacheable="false" like this :
<block class="Magento\Theme\Block\Html\Header" name="themes_header" template="html/header.phtml" cacheable="false" before="-">