I don't think it's a great deal to implement a "Search" field inside the recycle bin, so it would be no time consuming searching thru thousands deleted users.
Additional wishes for a search box:
You must be a registered user to add a comment. If you've already registered, sign in. Otherwise, register and sign in.