В окне создания перекрестной ссылки нет нужного заголовка

Совершенно верно. У меня в 2010 такие заголовки тоже в Перекрестных ссылках не видны.

Как только выполняю команду Изменить стиль, заголовок данного стиля в Перекрестных ссылках исчезает.

Если Вам необходим измененный стиль в Перекрестных ссылках, попробуйте сделать вот что:
1) Откройте Окно стилей - Параметры и проверьте, что у Вас установлен флажок Отображать как стили: Форматирование абзацев. 
2) Измените абзац в стиле Заголовок 1 непосредственно в тексте, как Вам необходимо. В окне стилей появится новый стиль с названием типа Заголовок 1 + Arial, 12 пт. Такой стиль будет виден в окне  Перекрестных ссылок.

Мне кажется, большой разницы нет. По моему мнению, вполне приемлемо использовать перекрестные ссылки на абзацы.
В практике нашей компании мы так и делаем.

Однако, при использовании таких корпоративных стилей у нас возникает одна проблема.
Любой пользователь может изменить эти корпоративные стили, если он пожелает (или случайно).
Пока нам не удается защитить такие корпоративные стили от изменения.
SSO, удается ли Вам решить эту проблему?

Кстати, о защите стилей только что была отдельная тема:
http://wordexpert.ru/forum/viewtopic.php?id=972

Люди при создании шаблона рекомендую стили "Заголовков 1-9" оставлять именно такими какими генерит их Word, в случае создания стилей типа:
- Заголовок 1 (ГОСТ);
- GOST Title 1;
- Мой Заголовок 1.
Вы обязательно столкнетесь с проблемой при нумерации объектов (рисунки / таблицы...) располагаемых в документе.

С защитой шаблона очень хорошо справляются стандартные средства Word:
1. Разработчик - > Защита - > Ограничить редактирование
2. Управление стилями - > Закладка "Рекомендации" - > Порядок сортировки "Согласно рекомендации" - > выбираете необходимые вами стили и присваиваете им приоритет, кнопочка "Присвоить значение..." чем меньше значение тем выше будет отображаться ваш стиль в списке стилей.

Например: Выбираем Заголовок 1-5 -> присвоить значение (устанавливаем "1") и в результате они будут в самом верху... так же поступаем с остальными (наиболее части используемым присваиваем маленькое значение...).

P.S. Не забудь разрешить стиль "Сетка таблица" именно он отвечает за стиль форматирования таблиц при копировании повторной вставке их в документ!

Alex_Gur, это немножко выходит за тему данного поста.

Разработчик - группа Защитить - Защитить документ - Ограничить форматирование и редактирование - ставим галочку "Ограничить набор разрешенных стилей"
После чего выбираем все необходимые нам стили, именно эти стили позже будут отображаться у нас в боковой панели "Стили" (которая вызывается сочетанием клавиш Ctrl + Alt + Shift + S). Нужно обязательно учесть для того что бы шаблон со своими стилями работал корректно существует ряд зарезервированных стилей самим Word-ом которые также нужно разрешить (например стиль "Сетка таблица", "гиперсылка", "Оглавление 1-Х" и т.д.).
Как только вы выбрали все необходимые вам стили в боковой панели они могут сортироваться в порядке "По алфавиту", "Согласно рекомендации" и т.д. что для нас не есть оптимальным. Нам (мне) нужно было что бы наиболее части используемые мной стили располагались вверху (боковой панели стилей), соответственно те что я использую резе ниже... Для этих целей мы:

Управление стилями - > Закладка "Рекомендации" - > Порядок сортировки "Согласно рекомендации" - > выбираете необходимые вами стили и присваиваете им приоритет, кнопочка "Присвоить значение..." чем меньше значение тем выше будет отображаться ваш стиль в списке стилей. Вот и все.

Защиту реализовываем в два этапа:
1. На уровне стилей (как это реализовать я попытался донести выше).
2. Так как Вы Alex_Gur, указали выше (шаблону оставить атрибут лишь на чтение).

Мне кажется более глобальной защиты не нужно.

Как Вы ранее упоминали есть тема на форуме:
http://wordexpert.ru/forum/viewtopic.php?id=972
Я по возможности именно в ней постараюсь это все описать (наверное все же не описать а снять и выложить ролик на youtube), мне кажется так будет более наглядно и проще (если это конечно кому-то нужно ).

Я ограничиваю набор используемых стилей в документе после чего сортирую их в желаемом для меня порядке.
Никакие стили в шаблоне редактировать не разрешаю!

Она полезная, но нажав ее можно увидеть что Word считает практические все стили рекомендованными... И как результат боковая панель стилей расползается на два / три экрана по вертикали (с прокруткой конечно)... плюс туда входят стили которые я не использую при формировании документа... ну и на по следок  с эстетической точки зрения как-то не красиво это...

Когда ролик сделаю, свистну . Там будет наверное яснее...
P.S. Я больше читатель чем писатель!