I am using the following versions:
libpoppler3-0.8.7-1.22
libpoppler-qt4-3-0.8.7-1.22
libpoppler-glib3-0.8.7-1.22

and have several PDFs which crash okular and evince when searching.

Anwendung: Okular (okular), Signal SIGSEGV
[?1034h(no debugging symbols found)
(no debugging symbols found)
[Thread debugging using libthread_db enabled]
[KCrash handler]
#6  0xb2e7f86b in Form::findWidgetByRef(Ref) () from /usr/lib/libpoppler.so.3
#7  0xb2e716b4 in AnnotWidget::initialize(XRef*, Catalog*, Dict*) ()
   from /usr/lib/libpoppler.so.3
#8  0xb2e719c4 in AnnotWidget::AnnotWidget(XRef*, Dict*, Catalog*, Object*) ()
   from /usr/lib/libpoppler.so.3
#9  0xb2e73e02 in Annots::createAnnot(XRef*, Dict*, Catalog*, Object*) ()
   from /usr/lib/libpoppler.so.3
#10 0xb2e7411a in Annots::Annots(XRef*, Catalog*, Object*) ()
   from /usr/lib/libpoppler.so.3
#11 0xb2eda466 in Page::displaySlice(OutputDev*, double, double, int, int, int, int, int, int, int, int, Catalog*, int (*)(void*), void*, int (*)(Annot*, void*), void*) () from /usr/lib/libpoppler.so.3
#12 0xb2ede2f0 in PDFDoc::displayPageSlice(OutputDev*, int, double, double, int, int, int, int, int, int, int, int, int (*)(void*), void*, int (*)(Annot*, void*), void*) () from /usr/lib/libpoppler.so.3
#13 0xb2fd3e65 in Poppler::Page::textList(Poppler::Page::Rotation) const ()
   from /usr/lib/libpoppler-qt4.so.3
#14 0xb3056a70 in ?? () from /usr/lib/kde4/okularGenerator_poppler.so
#15 0xb49b6e85 in Okular::Generator::generateTextPage(Okular::Page*) ()
   from /usr/lib/libokularcore.so.1
#16 0xb499a7f7 in Okular::Document::requestTextPage(unsigned int) ()
   from /usr/lib/libokularcore.so.1
#17 0xb49a47fa in ?? () from /usr/lib/libokularcore.so.1
#18 0xb49b015e in Okular::Document::qt_metacall(QMetaObject::Call, int, void**)
    () from /usr/lib/libokularcore.so.1
#19 0xb7f6e71b in QMetaCallEvent::placeMetaCall(QObject*) ()
   from /usr/lib/libQtCore.so.4
#20 0xb7f70281 in QObject::event(QEvent*) () from /usr/lib/libQtCore.so.4
#21 0xb68fd8fc in QApplicationPrivate::notify_helper(QObject*, QEvent*) ()
   from /usr/lib/libQtGui.so.4
#22 0xb690575e in QApplication::notify(QObject*, QEvent*) ()
   from /usr/lib/libQtGui.so.4
#23 0xb7a1e3ed in KApplication::notify(QObject*, QEvent*) ()
   from /usr/lib/libkdeui.so.5
#24 0xb7f60961 in QCoreApplication::notifyInternal(QObject*, QEvent*) ()
   from /usr/lib/libQtCore.so.4
#25 0xb7f615d5 in QCoreApplicationPrivate::sendPostedEvents(QObject*, int, QThreadData*) () from /usr/lib/libQtCore.so.4
#26 0xb7f617cd in QCoreApplication::sendPostedEvents(QObject*, int) ()
   from /usr/lib/libQtCore.so.4
#27 0xb7f8b36f in ?? () from /usr/lib/libQtCore.so.4
#28 0xb64a99a8 in IA__g_main_context_dispatch (context=0x80634c8)
    at gmain.c:2144
#29 0xb64ad063 in g_main_context_iterate (context=0x80634c8, block=1, 
    dispatch=1, self=0x8061ba0) at gmain.c:2778
#30 0xb64ad221 in IA__g_main_context_iteration (context=0x80634c8, may_block=1)
    at gmain.c:2841
#31 0xb7f8afb8 in QEventDispatcherGlib::processEvents(QFlags<QEventLoop::ProcessEventsFlag>) () from /usr/lib/libQtCore.so.4
#32 0xb6996785 in ?? () from /usr/lib/libQtGui.so.4
#33 0xb7f5f01a in QEventLoop::processEvents(QFlags<QEventLoop::ProcessEventsFlag>) () from /usr/lib/libQtCore.so.4
#34 0xb7f5f1da in QEventLoop::exec(QFlags<QEventLoop::ProcessEventsFlag>) ()
   from /usr/lib/libQtCore.so.4
#35 0xb7f61895 in QCoreApplication::exec() () from /usr/lib/libQtCore.so.4
#36 0xb68fd777 in QApplication::exec() () from /usr/lib/libQtGui.so.4
#37 0x0804e0cf in _start ()

These documents come from one of the biggest libraries I guess http://www.jstor.org/stable/3059723

P.S.
It does work with kpdf and libpoppler2-0.6.4-2