Проблема в кеше.
Лезем в компонент bitrix:menu
и видим там
($arParams["MENU_CACHE_USE_USERS"] === "Y"? $this->getGenerationCachePath($USER->GetID()): false)
Решение: Добавить в вызов компонента меню параметр
"MENU_CACHE_USE_USERS" => "Y", меню станет кешироваться для каждого пользователя отдельно.
В качестве бонуса получаем огромный кеш меню, если в нем много пунктов и на сайте много пользователей.