со временем исчезнут, если нужно сделать в срочном порядке, то в google webmaster tools есть раздел, где можно "удалить" не нужные/не существующие страницы
Попробуйте сперва проанализировать оба варианта от лица посетителя сайта (потенциального клиента), какая навигация для вас была бы более удобной и логичной, в большинстве случаев это и будет лучший вариант для СЕО. Если список, например, громоздкий и товар "разношерстный", то логичнее его конечно разделить на тематические группы
в google webmaster tools есть возможность указать, что сайт "переехал" на новый домен, возможно и в яндксе есть подобный сервис, наверное это будет лучшее решение проблемы в данной ситуации
я бы не стал использовать исключительно высоко-конкурентные фразы, отдачи скорее всего не будет, лучше взять за основу что-то уникальное (например название сервиса) + какие-то "незаезженные" слова по теме (например слово "мульты" более чем в 10 раз реже используется, чем слово "мультфильмы"), ну и разбавить это все какой-то уже более юзабельной фразой типа "смотреть онлайн".
Конкретно на такой вопрос не ответить, все зависит от программы, ищите форумы, которые ближе всего по тематике, там и будут ваши потенциальные клиенты. А дальше на что фантазии хватит, например спец. условия для участников форума и так далее.
