The first query from Ernad does not work because the query in the first place does not include deleted contents. Adding an extra filter does not help.
The only way to query for deleted content is like Einar is doing. Here the built-in filter, that excludes deleted content, is disabled so that all content is returned.
BTW: The same applies if you want to query for content across multiple languages in the same language. Just set the flag related to languages on the AQL alias object.