Как сделал бы я (в порядке убывания).
Создать временные посадочные с похожими товарами и переводить на них по 301 с удаленных страниц. С этих посадочных уводить человека на нормальные категории и товары.
Просто по 301 с удаленных на оставшиеся категории товаров и товары.
404, но оформленную так, что бы чкловек по ссылкам смог перейти и на похожие товары и на похожие категории.
Просто 404