Я бы сделал так:
1) ссылки в зависимости от IP-адреса нужно генерить в файлах [URL=http://dev.1c-bitrix.ru/api_help/main/general/menu_5x.php].тип меню.menu_ext.php[/URL], иначе карта сайта будет неправильной.
2) придётся либо отказываться от кеширования меню вообще, либо разбираться с ним. Штатное кеширование, скорее всего, в вашем случае будет работать неправильно.