Se você estiver em uma situação em que a reinicialização não esteja sempre liberando o espaçamento, eu reinicializaria no modo de recuperação e usaria du como descrito acima para ter uma ideia de para onde o espaço está indo. Eu costumo fazer "du-sc * | sort -n" como uma forma rápida e suja de fazer este tipo de investigação (suja devido a problemas com arquivos ocultos, etc., como discutido acima). Comece na raiz e trabalhe para baixo.
Eu concordaria que este é um problema muito estranho. Talvez tente desativar seletivamente os serviços para ver se você consegue pará-lo? No que diz respeito à indexação, as únicas coisas que rodam em todo o sistema como padrão que eu posso pensar devem ser localizar / mlocate. Há também o apt-xapian que indexa pacotes, mandb que indexa man pages.
Você está fazendo o login nesta máquina com uma sessão de desktop? Em caso afirmativo, o problema é interrompido se você fizer login (pelo menos graficamente)?