There is an “index cache” kept that contains the state of the local repository. When syncthing starts, it reads the index and compares to the current state of the repo. Files that are in the repo but not mentioned in the index are new. Files that are mentioned in the index but not present on disk have been deleted.
The process is basically the same for each rescan when running, except the index is already in memory and represents the state of the repo at the previous scan.
Files that we think we deleted but then pick up on the next scan will be seen as “new” again.