Моя компания делает нечто подобное с нашей базой кода (C, а не C #), которая насчитывает около миллиона строк. Шаги пошли примерно так:
1) Напишите несколько автоматических тестов, подобных описанным вами, которые выполняют тесты системного уровня.
2) Реализуйте правило, согласно которому новый код должен иметь модульный тест.
3) Когда в области есть несколько ошибок, процесс исправления этих ошибок должен включать в себя написание базового модульного теста.
Дело в том, что 3 не должен требовать полного модульного теста (если людям будет легче это делать). Если вы перейдете от 0% покрытия тестом к 40% покрытия конкретного модуля, то вы добились большого прогресса.
Хотя через 6 месяцев у вас может быть до 5% от общей базы кода, но 5% - это код, который больше всего меняется и в котором вы, скорее всего, будете вносить ошибки. Код, над которым я сейчас работаю, примерно на 60% покрыт интеграционными тестами, а 15% (построчно) - модульными тестами. Это не так уж много, но это дает значительную ценность, и наши усилия по разработке выиграли от этого.
edit: В ответ на один из других комментариев текущий набор интеграционных тестов, который мы выполняем, занимает в настоящий момент около 14 часов. Сейчас мы планируем запустить некоторые из них параллельно, чтобы ускорить их.