Внутри заголовков H1-H6 можно использовать теги span и br.
Ни в коем случае нельзя использовать в нем блочные элементы вроде div. Пихать small - безграмотно с точки зрения семантики.
Как пишут выше сохраняйте оригинальные URL, если они не совсем уж страшные.
Второе решение - настроить редиректы, но пока поисковики их учтут пройдет много времени.
Старый сайт или новый - неважно для поисковиков. Главное чтобы контент находился по старому пути или работал редирект.
Так что решать именно вам - удобно ли работать с текущим сайтом, устраивает ли дизайн. Если нет, то не разумнее ли сменить дизайн без смены движка и т. д.
Для поисковика важно минимизировать количество запросов к файлам.
Если при включении плагинов кэширования возрастает количество запросов к БД и время загрузки страницы, значит ты что-то делаешь не так.
У меня на одном проекте Гугл индексирует за пару минут, а Яндекс - пару недель.
Насчет вашего случая, возможно это дубликаты или какие-то мусорные страницы, исключенные из поиска.
Прогонял сайт через 1ps.ru пару лет назад. Особого эффекта это не дало.
И еще нужно понимать, что на самом деле это не каталоги, а такие же сайты, установившие себе страничку со ссылками. Как писали знающие люди, нужно прогонять с нормальными списками каталогов через нормальное ПО.