Nothing's working for me ... but, if you read through this entire post, you'll find something new and interesting!
I'm using High Sierra 10.13.6. Preview version 10.0 (944.5). Files that I (probably) used to be able to search before are (no longer) searchable. I tried Cmd-W, closing and reopening Preview, change a Preference and restarting Preview, deleting ALL com.apple.preview.plist files. Nothing works.
I can search some files fine, but not others with Preview. Here's something further interesting ... the files I CAN search with Preview I can also search with Adobe Acrobat DC. The files that don't work in Preview don't work with Acrobat either! And the same is true of Safari and Google Chrome using File>Open File ...
AND, using Preview and Safari "Export as PDF ..." doesn't work either! Files still remain unsearchable.
However, I was able (with some errors) to use ABBYY's FineReader to "convert" an unsearchable PDF to a searchable PDF file.
A very very strange bug. There certainly appears to be something wrong with the unsearchable files.
I think I found out what it is ... apparently these unsearchable files are not in fact PDF files, but are IMAGES! I installed a free trial of Adobe's Acrobat Pro DC, which I do NOT want to pay for. But I opened an unsearchable file, and it said, "This page contains only an image. Would you like to run text recognition to make the text on this page accessible?" I converted the file to "Editable text and images". VOILA! The resulting file is searchable, even in Preview!
Now the mystery is ... "why and when did my previously searchable .PDF files become image files?"
Does anybody have an easier way to convert such files back into true PDFs?