В любом случае, даже если настроено 404 везде, то один из важных шагов, это пересчитать все свои странички)) При малых объемах сайта это выход. Если сайт огромен, и нет 410 ответа, то это капец
Если сайт на какой-то популярно CMS, скорее всего вариант пересчитать странички подходит. Под пересчитать я имею ввиду сделать табличку в бд, в которой храняться урлы (если такой таблички нет по умолчанию)