I created a list that has four lookup columns, and all of them lookup
user info and show the display name. When I go to search, though, it
won't find anything from those rows that contain the names of the
people I'm searching for.

Example: Joe Smith is a site user. I have selected his name from a
lookup column for a list entry. This list entry shows in this
particular view. When I search for "Joe" or "Smith" or even "Joe
Smith", I get no results.

Does it not see these user info names as text? Why is this happening
to me??