I thought that this could be done by a custom message filter. Then I had a look, and it turns out, that currently this can not be done with a custom message filter, because there is no way to select deleted messages or to select all messages of a certain folder (a folder with a deleted messages).
I suggest to improve the filter options so that deleted messages can be selected.