Poderia ser seu sistema apenas não está à altura da tarefa? Eu não uso o MySQL (SQL Server aqui), mas eu sei a dificuldade de indexar uma tabela de entrada de 800 milhões. Basicamente .... você precisa do hardware certo para isso (como em: muitos discos rápidos). Agora eu uso quase uma dúzia de Velociraptors e a performance é ótima;)
SQL Servers (não como MS SQL Server, mas como servidores de banco de dados usando SQL), vivem e morrem com acesso ao disco, e os discos normais simplesmente não estão à altura da tarefa de operações maiores.