Крупный проект и валяться 404 ошибки

Ну, будут редиректы "валиться". В чем проблема-то? Что значит "валяться" и в чем именно вы видите проблему?

Предлагаю вам исключить возможность удаления профайла компаний — тогда ошибки появляться не будут. Вместо удаления, компании можно отмечать как «удалённые» — в базе данных и на самой странице компании соответственно. Например, как тут — http://bandhunters.org/profile/view.aspx?id=383 — большое красное предупреждение о том, что профайл удалён и никакой ответственности мы за него не несём.

А так — на практике вы иначе никак не избавитесь от 404-к. Даже замена их на 410 бесполезна — Google Webmaster Tools всё равно их помечает ошибками.

Большое количество 404 ошибок, примерно 10000-15000