Может быть робот просто не успел пройти по вашим страницам? Яндекс-то откуда знает, что они не удалены, он же не нон-стоп ваш сайт мониторит, а раз в какое-то время (может быть даже раз в неделю или ещё реже). Зайдите в Яндекс.Вебмастер в раздел Индексирование -> Переобход страниц и укажите там удалённые страницы. Робот Яндекса постарается просканировать удалённые страницы в приоритетном порядке и отметит их 404 ошибкой, после чего удалит из выдачи.
