This question is over a year old. The OP didn't post a link to the original PDF. I found another PDF that appears similar: https://skemman.is/bitstream/1946/35610/1/BS_DSE_KJ.pdf
Here's what I found:
In Ventura, I see the same problems described. If I search for "hjartslá", I find nothing.
In Sonoma however, things are different. If I search for "hjartslá", I do find all of the matches.
Just for fun, I went ahead and installed Adobe Reader in my Sonoma VM. Right off the bat, Adobe Reader complained about some vague, unspecified problem. Don't know what that was. It's also noticeably slower than Preview. But it does also successfully find "hjartslá".
But then I did a test. I changed the search string to "hjartslt. As expected, no matches were found. I only did this to clear out the search settings. Then, I searched for "hjartsla" (changing á to just a). Adobe Reader still found the matches. Is that better or worse? Certainly, it is a more powerful search engine. In addition to this kind of fuzzy match, it has lots of other options.
But remember, I'm actually testing a different PDF file. Preview can find the text in my PDF. So, it's possible that the OG PDF could be improperly constructed. Another possibility is that my Sonoma 14.5 Preview version 11 (1056.5.1) has fixed this particular bug. Considering Apple's track record on fixing bugs, I think it's more likely that the original PDF was wrong. Recent versions of Apple Preview over the past few years have had some nasty bugs. But they appear to be fixed in Sonoma.