List of steps to reproduce (step by step, including full links if applicable):
Try a WQS query looking for Q531659 and Q21504507 (where I noticed the problem).
What happens?
The query returns a lot of claims for those two items.
What should have happened instead?
The query should have found nothing, these two items have been deleted three days ago: https://www.wikidata.org/wiki/Q531659, https://www.wikidata.org/wiki/Q21504507
(Note that when testing the query, once it returned just two rows with one wikibase:timestamp claim for each item; no idea if the result depends on the serving server from a cluster or what.)