I have this exact same situation with my Youtube history. I used to be able to search it in Google's history search, but that only shows a subset of results.

If I want to really search for the title of a random video I saw 5 years ago the only option is to download a raw CSV of my history and use grep :(