Unicode search in PDF works fine, there are just a few issues that can cripple it for specific files, or specific files using specific PDF implementations. The following is advice for anyone working with the format, it should not be construed as making excuses for how PDF does things. It's a ginormous format with a ginormous spec that's been around for a very long time and has accumulated a lot of baroque qualities over the years. So I don't mean to condemn it, but I'm not exonerating it either. It is what it is, and if you have to work with it this might be useful. Anyhoo:

Regardless of what one thinks of their other qualities, if a PDF can be searched in Adobe Reader or Acrobat, then the file is probably OK but the PDF reader that you were trying to search it with has a bug on its end (or more likely, some unimplemented dark corner of the PDF spec).

On the other hand, if the file isn't searchable via Reader/Acrobat, then the problem is most likely with the authoring of the file itself. The most common thing that breaks searching is when instead of embedding all fonts used, a PDF refers to fonts by name from the local system. This can cause unpredictable issues when reading the PDF from another OS that can't resolve those font names.

Another common breaker of search that seems to be much more common with TeX are workflows which somehow produce PDFs that have embedded Type 3 fonts. Type 3 fonts represent glyphs using PDF drawing instructions. It's less a file format than something that only exists as an embedded font within a PDF, but I've only seen them in the wild when authored by pdflatex or similar. It seems like TrueType or OpenType are the most reliable formats to embed across the most commonly used PDF implementations, but that's an educated guess. Type 3 font support is spotty in non-Adobe implementations.

Finally, font subsetting might screw up search. Most software that knows how to produce PDFs can produce PDFs with embedded but subsetted fonts. This means the software that created the file embedded TrueType fonts (for example), but created a special version of the font for embedding that only contained the glyphs used in the PDF. Depending on the quality of the software used to do the font subsetting, the output PDF might not retain the mapping of glyphs back to Unicode characters. If that happens, text using that font in the PDF becomes unsearchable, but the PDF remains renderable.

None of this is meant to excuse the shortcomings of the format, it's clearly overcomplicated and fragile. But when I've seen problems with searchability of PDFs, it's most often been with the software that was used to create the files, or how that software was configured by the author. And when it is a problem with the authored file itself, it's almost always because of fonts. Either the fonts aren't embedded, or they're embedded in a slightly oddball format that's in spec for PDF but not perfectly, universally supported by all of the various non-Adobe PDF implementations.