You need to rebuild your Search Index.
It will take a very long time in most cases, but the board should be able to stay operational, I believe. Though I would suggest doing it at a quieter time as it is rather resource intensive.
Admin CP > Tools > Rebuild Caches > Rebuild Search Index.