Normalmente, é realmente a melhor idéia reinstalar o sistema, pois ele perdeu o status de confiança e não há uma maneira fácil de confirmar se o sistema não está mais corrompido, mesmo após a remoção de alguns dos malwares.
Se houver preparações para casos como a realização de checksums de estados confiáveis que são comparados regularmente com o sistema em execução, você poderia avaliar tal verificação e retornar a um estado confiável.