Não tenho certeza se algum dos leitores de pdf suporta indexação de texto - provavelmente porque a indexação em si seria bastante cara e os arquivos em pdf abertos e fechados 'ad-hoc'
No entanto, eu fiz alguns testes e posso ver que okular - o visualizador padrão do KDE - tem uma busca muito mais rápida do que o evince (o visualizador padrão do Ubuntu). Ou seja Demora talvez um segundo para escanear todo o documento de 500 páginas, enquanto o Evince gasta ~ 5 segundos na mesma tarefa.
Você pode instalá-lo digitando
sudo apt-get install okular
(ou apenas procure por ele no Centro de Software )
se este for o primeiro programa do KDE na sua máquina, será necessário instalar um pouco de dependências, mas pode valer a pena - estou achando os programas do KDE mais capazes do que os do Gnome ... O Okular suporta pdf anotações, por exemplo, que também é útil às vezes.