Okular's search fails to find non-ascii umlaute. I guess it could be a bug in libpoppler since evince fails this too. Example pdf I noticed the bug in: http://www.math.ethz.ch/education/bachelor/lectures/fs2010/math/nm/skript.pdf p.ex.: search for 'ä'

for evince, there is a discussion on the same issue
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=427119
I had an Idea on how to solve this, filed evince upstream bug
report/enhancement here: https://bugzilla.gnome.org/show_bug.cgi?id=618971

severity 582099 wishlist
thanks

The problem is not within okular, but within the pdf files generated by TeX
with the Computer Modern font family (which does not contain umlauts so TeX
combines them from different glyphs). Even Adobe Reader has the same problem.