"Проблема" в кривом кешировании самой структуры меню.
в главном модуле в классе CMenu в методе RecalcMenu
Зачем оно там нужно не понятно, и искать место где это кеширование отключить как-то влом ).
Ниже код, который я бы просто убрал.
$arMenuCache = false;
$bCached = false;
$bCacheIsAllowed = CACHED_menu!==false && !$USER->IsAuthorized() && !$this->MenuExtDir;
if($bCacheIsAllowed)
{
$cache_id = $GLOBALS["DOCUMENT_ROOT"].",".$this->MenuDir.",".$this->MenuExtDir.",".$this->type;
if($GLOBALS["CACHE_MANAGER"]->Read(CACHED_menu, $cache_id, "menu"

)
{
$arMenuCache = $GLOBALS["CACHE_MANAGER"]->Get($cache_id);
$bCached = true;
}
}