Hola de nuevo:
Por el resultado del EXPLAIN, creo que no tienes definidos llaves ni índices lo cual no es nada bueno. Dale un vistazo a esta liga
http://dev.mysql.com/doc/refman/5.0/es/explain.html
Ahí se detalla lo que te está arrojando el EXPLAIN, qué problemas tienes y las posibles soluciones.
Dices que la consulta normalmente se tarda muy poco, pero en ocasiones se tarda demasiado... podrías revisar por ejemplo si el comportamiento se da en horas pico, si coincide con algún otro proceso en la BD o en el servidor que pudiera bloquear temporalmente la tabla. hay muchas otras cosas que tienes que revisar.
Saludos
Leo.