L'un des plus gros problèmes de Baloo (le logiciel qui s'occupe de l'indexation des fichiers), c'est qu'il est peu configurable et que les paramètres par défaut s'adaptent très mal aux structures un peu bizarres.
Je m'explique: Baloo cherche par défaut dans le Home, et je suis à peu près certain qu'il ne suit pas les liens symboliques (en tout cas la dernière fois que j'ai testé). Si comme moi, tu as très de choses dans le Home et tout sur une autre partition, c'est loupé du coup.
Par contre, tu veux modifier le fichier "~/.kde/share/config/baloofilerc" et ajouter le lien vers d'autres dossier à la ligne:
folders[$e]=$HOME/
Par exemple, moi, mes fichiers sont dans /home/Data, ça donne:
folders[$e]=$HOME/,/home/Data/