How can an administrator find the UID of a user that's been deleted with the
By looking at
/etc/passwd in the backups taken of your system from the day/week/period before the user deletion.
userdel was used with -r, then both the home directory and user's mail spool have gone. If it wasn't used with -r, check for the user's mail spool, or perhaps a crontab if you're very lucky.
If there are no backups, and no obvious files owned by that user you can check, then you'll need to scout around places like
/tmp and look for files with UID's as owners and try and work it out - but really, your backup is your best bet.
Edit: as jw013 points out you could also use
find / -nouser to find files which have no matching user for the file's UID.