По-умолчанию на каждую страницу Битрикс создает свой кеш меню.

Однако данное поведение можно отключить при вызове компонента bitrix:menu добавлением скрытого недокументированного параметра 
"CACHE_SELECTED_ITEMS" => "N" 

Проверьте установлен ли у Вас данный параметр и при необходимости уберите его.

Ссылка на курсы Битрикса - http://dev.1c-bitrix.ru/learning/course/?COURSE_ID=43&LESSON_ID=5402