Hello,
one thing to keep in mind is that Lucene (and SOLR in 4.x) can be out-of-synch with the real state of the database, depending on how they are set up (tracking / index update intervals) and how long it takes to update the index for one specific set of changes. The search with fts-alfresco on workspace://SpacesStore should normally not return any deleted nodes, but may contain some when the deletion just occured and the indexer did not yet have a chance to remove them from the index. Since this can occur (and will likely do so sometime in a high load situations), you should always take care to check your search result nodes for existence (as an extension programmer), before performing any operations on them.
If your issue is consistent, reproducible and deleted nodes are retained in the index longer than the default 5-15 seconds between indexer runs, it would be worth looking into your use case and your configuration.
Generally speaking, which version of Alfresco are you using / does your issue occur on?
Regards
Axel