С Яндексом все достаточно просто и заморачиваться не надо, с гуглом все немного сложнее и при возврате 404 бот иногда начинает домогаться этой страницы еще очень долгое время, расходуя и без того скудный в последнее время бюджет сканера.
В свое время я достаточно долго мучился с тем, чтобы бот отстал от моего удаленного блога и не сыпал гору ошибок в журнал. Бот возвращался и возвращался, сканируя 404 снова и снова, причем, несколько раз в день. Обращался даже к гуглеру, который передал куда-то вопрос, стучаться в блог перестал, но со временем появились какие-то другие страницы, куда он любил долбиться чуть ли не ежедневно.
Решение очень простое. По умолчанию на отсутствующие страницы пусть отдает 404. Это обозначает просто, что страницы нет. Т.е. была и пропала, какие-то другие условия привели к тому, что ее в данный момент нет. Может, еще когда-то появится. Однако, если вас взломали и вы занимаетесь какой-то чисткой именно с целью "удалить навсегда", то рекомендую использовать 410. Это обозначает, что страница была и вы ее целенаправлено удалили.