404 Not Found — самый распространенный ответ сервера, основная причина — ошибка в написании адреса Web-страницы. Сервер понял запрос, но не нашёл соответствующей страницы.
410 Gone — ответ сервера, когда страница раньше была доступна по указанному URL, но затем была удалена и теперь стала недоступной.
Если серверу известно что по данному URL адресу был документ, но теперь его нет (он удален) — то желательно использовать код ответа 410. Ответ 404 может использоваться если пользователь ввел адрес не существующей страницы и на неё нет внешних ссылок. Если есть вероятность, что документ в ближайшее время может быть восстановлен, то лучше клиенту передать код 404. В противном случае — если документ удален на всегда, лучше использовать 410 ответ. Иначе это может привести к появлению в Google Webmaster Tools ошибок вида:
Google detected a significant increase in the number of URLs that return a 404 (Page Not Found) error. Investigating these errors and fixing them where appropriate ensures that Google can successfully crawl your site's pages.
Вероятнее всего страницы со статусом 404 поисковый робот обходит несколько раз, прежде чем страница будет удалена из индекса полностью. Поэтому при необходимости используйте ответ 410.