People Tab Search: How It Works?

Users report that entering keywords in the People tab doesn't return all expected matching records, even when they know users exist with those terms. Questions this answers: Can I use % as a wildcard when searching the People tab? Which user fields does the People tab search look at? Why doesn't People tab search find users I know exist?