The search parameter deleted is only available for moderators. As a non-moderator, when I enter any combination of deleted parameter, like deleted:1, the query returns all posts. It seems that a search without parameter is executed, so that every post matches. Normally this cannot be done. Hitting enter in search box without input as an example returns no result (0 posts).
So my suggestion is to handle the deleted parameter for non-moderator in that way that it behaves like an empty search via search box and returns no result or execute it as a quoted search "deleted:1".
Example on meta.
