As far as I can see in my own PhotoLab database, PhotoLab does not clean up the database if items have been removed outside of PhotoLab. PhotoLab search looks for matches in the PhotoLab database rather than in folder hierarchies. Re-Indexing does not help either, which means that the database accumulates things that are long gone…
To remedy such differences, a few feature requests have been made already…