There’s a boolean operator for the search that’s not mentioned on the searching help page:
deleted:
yes/true/1 returns only posts that have been deleted; the default no/false/0 excludes deleted posts from the search. This operator does only return your own deleted posts regardless of theuser
operator and is useable only by users with the Access To Moderator Tools privilege.
The above should be added in the “Boolean Operators” subsection.