Ainda não tenho ideia de qual foi a causa raiz do problema. No final, suspeitei que a CPU do sistema fosse muito fraca (alta carga média, alta carga cpu).
Hoje eu atualizei o sistema para o Ubuntu 10.04 e o problema parece ter se resolvido. O desempenho ainda não é tão estável quanto eu gostaria, mas em média ele melhorou em pelo menos 10 vezes.