Раньше на сервере к адресу добавлялась сессия.
Яндекс проиндексировал все с сессиями.
Теперь сессии убрал, а яндекс всеравно продолжает ходить по этим страницам, а по нормальным адресам (без сессий) не ходит.

Вопрос, как заставить его ходить по правильным страницам и не ходить по страницам с сессиями?

Есть версия:

При любом посещении сайта делается попытка определения User-Agent'а. Если это обычный посетитель, сессия передается через кукиз (если нет поддержки кукизов, через сессию в URL'е). А если это один из известных поисковиков (в частности Яндекс), делается так:
Для каждого поисковика назначается определенный идентификатор сессии, который ему всегда выдается. А при обращении с другими идентификаторами выдается 404.
В результате при индексировании в базе хоть и остаются URL'ы с сессиями, но не создаются дубликаты, что и составляет главную проблему.

Можно еще попробовать просто выдавать поисковикам URL'ы без сессии вообще (опять же используя User-Agent). А при обращении по URL с сессией, всегда выдавать 404.

Это будет работать?