Essa dica é pra quem usa KDE, e como eu, às vezes esquece o que tem instalado no PC...

Para minha surpresa descobri esse utilitário sem querer ontem enquanto navegava à toa pelos menus do KDE. Esse tal de Kappfinder faz exatamente o que eu estava procurando há um tempo atrás. Ele procura no seu computador por programas instalados que não tem seus devidos links nos menus do KDE, depois te dá um relatório. Você escolhe quais quer que ele crie o link e ele os cria, tudo simples, fácil e rápido!

Pra rodar o utilitário, no console digite:

$ kappfinder

Ou então vá em K -> System -> Menu Updating Tool

Espero ter ajudado alguém!
Abraços

Obs: dica testada no KDE 3.3, não sei se versões anteriores possuem esse utilitário.