Olivier Berger <olivier.berger@telecom-sudparis.eu> writes:

>
> In any case, there has been a change in the way this worked.

That's strange, but since it is currently working as we expect, the main
question is whether we should change how excludes work.

>
> For the moment, I'm using the following saved search :
>     (tag:deleted or tag:spam) and tag:deleted
> which will display the deleted mails.

Right. For me it would be less confusing to write

       (tag:deleted and tag:spam) or tag:deleted

I agree that the interaction of excludes makes (either version of ) this
search look a bit strange.