Sort the emails in alpha order and then scroll down to the location of that person in the list

I don't want to do that because I want to search inbox and sent, etc. That would remove the benefit of being able to search

Maybe I will uninstall and re-install Thunderbird. Can I do that and keep my folders, settings, everything?

You would have to treat it as if you were moving a profile: https://support.mozilla.org/en-US/kb/profile-manager-create-and-remove-thunderbird-profiles

The Profiles should be backed up before attempting anything - and usually once a week in case of crashes. I doubt if the re-installation will resolve your issue but you could try over-installing first.

If you want the problem to be re-considered please post in this thread so that it will go back onto the list of questions needing solutions.

Maybe it has something to do with my file structure?

If you can look at the attached screenshot, you can see it returns results from all of the folders except the sent folders. I get results from the Inbox, 2024 folder, Draft folder, etc.