До появления JDK 7 в Java не существует неродного механизма для обнаружения событий, связанных с файлами (включая удаления). Тем не менее, даже если бы вы смогли обнаружить удаление файлов, вам все равно понадобился бы некоторый алгоритм для синхронизации ваших индексов при запуске приложения.
Когда мы делаем такие вещи, мы обычно фиксируем путь + дату изменения + длину файла в индексе (мы используем jdbm btrees). Тогда для повторной индексации необходимо выполнить итерацию дерева папок и индекса одновременно. Когда вы найдете в индексе запись, которой нет в дереве папок, удалите ее из индекса. Когда вы найдете в дереве папок запись, которой нет в индексе, добавьте ее в индекс. Если вы найдете запись, которая есть в обоих, проверьте дату и размер изменения.
Так что, пока у нас не будет jdk7, вы в значительной степени застрянете с решением на основе опроса (то есть обновите индексы каждые XX секунд).
Обратите внимание, что jdk7 (в дополнение к мониторингу папок) значительно улучшит производительность при переборе файлов (текущие операции с файлами действительно медленны по сравнению с тем, что вы можете делать изначально).