Viewing a pdf with Preview, I do cmdF to bring up a search box and then enter a word and hit enter.
Basically nothing happens even if it's a word that's obviously present. Sometimes if I smash my hands all over the keyboard and spin around in my chair three times the search suddenly starts working again, but I haven't figured out how to do that trick reliably.
For what it's worth: in my case the problem seemed to appear when opening a pdf from Finder. Opening the same file via File>Open in Preview "solves" the problem. Unbelievable something as simple as this is still not fixed in Catalina 🙄
I experienced this issue as well. For me at least, the problem was that I got stuck searching the annotations or table of contents, and so generally didn't find what I was looking for there. I was able to resolve this by clicking on the x box in the search panel to exit out of the old search and go back to searching through the whole document.