Threads that are deleted are NOT removed from the search index automatically, in order to save CPU time.

You should rebuild the search index using the Index option in your UBB cpanel. That will remove the dead posts.