@psubsee2003 is describing what I noticed too: When a option is ignored, and it is the only option used to search, the search returns all the posts. The difference with "deleted:" and other options, is that when other options are ignored you notice that.
For example, if I use "votes:2" the result page shows this.
If I use "votes:q123" the result page doesn't show any option as being used for the search.
With "deleted:1" there isn't any way to know if the option is applied, or not. I can know it from the background shown for the posts.
When I use "deleted:1" or "votes:q123" on this site, I get 135,086 results in both the cases; when I use "user:me votes:q123" or "user:me" on the same site, I get 1,185 results in both the cases.
I am moderator on Drupal Answers, and on that site I am allowed to search for deleted answers.