Это вообще больная тема. Пагинированные страницы в поиск лучше не отдавать, они не всегда постоянны, что ни к чему, кроме расстройства юзера, не приведет.
Раз уж у вас возникла такая проблема, отдайте 404, и в его тексте напишите, что указанной страницы со списком товаров нет, но вот для пользователя ссылка на внутренний поиск по сайту, который пощет то, что искал он сам поисковиком. Т.е. человек, щелкнув по ссылке, перейдет на страницу, где, возможно, нужные ему товар все же выведен.