[CentOS] Finding user's files

This is among the things we need to do when a user leaves, and it's a
larger question than it sounds. Our Office has many servers, with a good
number of fileservers for projects, with large filesystems (i.e. 10's of
TB). Can anyone think of a way *other* than running what's probably a
many-hour long find / -user on all our systems, which is really intensive,
to find all the files own by a given user?

Locate would be great, but from the man pages and what I can find online,
it only stores filenames and paths.

        mark