По кривости рук промахнулся в MC и удалил половину каталога /usr...
Как провести проверку имеющихся в базе пакетов и переустановить пострадавшие?

Для поиска пакетов с недостающими файлами можно посмотреть в сторону apt-file, правда автоматически он этого, естественно, не сделает и придется почитать мануалы.
С другой стороны, если нет сильного ограничения по трафику или если в кэше апта хранятся пакеты, то
# dpkg --get-selections | grep -v "deinstall" | awk '{print $1}' | xargs aptitude reinstall
может быть вполне себе альтернативой.