datatraveler,
esto eran cosas fáciles.
Cita:
Iniciado por datatraveler 
Una pregunta, si quiero hacer consultas que incluyan más tablas, es recomendable que también indexe los campos que aparecen en las cláusulas y en las uniones, verdad?
Sí, pero dependerá de algunos factores. Si son tablas MyIsam tienes que indexar tú los campos que empleas como foreign key (en las tablas InnoDB no es necesario, pues ya lo hace el programa), los que usas en las uniones mediante join. Respecto a los empleados en los where te diré que eso dependerá de la cardinalidad. Si la cardinalidad es muy baja, como en los bloqueado, etc., de tu base, no será necesario ni conveniente hacerlo, pues el índice no será usado y ocupará espacio.
Un par de consejos más
1) haz pruebas cambiando el orden de los datos buscados tras el where para ver cuál es más rápido.
2) usa EXPLAIN antes de la consulta para ver qué nos falta por mejorar. Si analizas ese explain podrás sacar alguna conclusión acerca de cómo mejorar la consulta.
Cita: Por último, qué le harías a la estructura de las tablas?
Si saber para qué sirve cada tabla y cuáles son tus objetivos, no puedo ayudarte mucho. Me da la impresión de que estás usando en las tres tablas datos que podrían estar en una, pero tampoco estoy seguro con la información de que dispongo; veo tipos de campo que podrían ser distintos, aunque, como te digo, no puedo aconsejarte sin disponer de mayor información. No sé cuáles son las entidades, sus atributos, etc., cómo has aplicado las reglas de normalización.