Что делать, если поисковик показывает старые ссылки?

Доброго времени дня, гуру маркетинга!

Помогите разобраться с ситуацией. Модернизировали сайт, был один домен и все страницы начинались с имени сайта, теперь в нем много поддоменов (вася.ком) и каждый поддомен начинается соответственно со своего имени (злой.вася.ком, добрый вася.ком и т.д.).

Теперь ситуация такая, при запросе поисковая система (любая) выдает ссылку типа вася.ком/1238/456 (такая ссылка должна вести на старый дизайн сайт, но его уже нет). При переходе по ссылке мы попадаем на главную страницу сайта с новым дизайном вася.ком, где маячит ошибка, что данная страница недоступна. Но если дописать допуск на старый дизайн (старый.вася.ком/1238/456), то попадаешь на страницу сайта со старым дизайном. программисты, делавшие сайт и переносившие все сказали, что для гугла достаточно почистить всевозможные истории, выйти из почты ,снести все нафиг и поставить заново и будет нам счастье.

Теперь вопрос: счастье от этих действий не пришло, поэтому надо делать что-то другое. Возможно что-то нужно сделать со "старым" сайтом, или писать гуглу, или направить все силы на "новый" сайт? или может быть что-нибудь еще. Хотелось бы разобраться в ситуации и программистам давать конкретные задания.

Спасибо за терпение и буду благодарна за какой-нибудь полезный ответ.