Update: So I mustered the courage to try the search engine, because it was looking not very much like a scam, and it becomes very apparent as soon as you use it that non-deleted videos are also indexed.
Yes, the database contains all the videos, both deleted and active ones. Or rather, not the videos themselves, but the metadata and links to the video files in the web archive. I don't have servers large enough to store the videos themselves.