Все сообщения об ошибках 404 исходят от Google Bot или это реальные пользователи? Если первое, возможно, вы правы в том, что они использовали старую карту сайта или повторно сканировали старые URL-адреса, чтобы убедиться, что они действительно недействительны. Кто знает, как работает бот, но в целом он делает все правильно - ваши 404 страницы не отображаются в результатах поиска, так что кого это волнует?
Если они настоящие пользователи, вы должны узнать, откуда они пришли, используя заголовок реферера. Надеюсь, тогда вы сможете найти источник проблемы. Заголовок реферера иногда бывает пустым, но для такой большой выборки я ожидаю, что будет доступно довольно много данных.