Despite the message:
Note: only content you own is returned when searching for deleted content
I'm able to search a specific user's deleted content using a search query such as:
user:X deleted:1
Where X
is the user ID:
As far as I know not even 10K+ users should be able to do this.