Em lxde, gosto de usar o pacote xfce4-appfinder.
Este pacote xfce requer uma ou duas bibliotecas xfce, tem apenas 180kbytes e fornecerá a você um aplicativo de pesquisa idêntico ao usado pelo xfce: link
Você deve ver este localizador de aplicativos no menu de aplicativos lxde. Eu prefiro adicionar este item no meu painel inferior como um lançador.
PS: Você também pode executá-lo a partir da linha de comando usando o xfce4-appfinder