Following up on this post;
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:
X is the user ID:
As far as I know not even 10K+ users should be able to do this.