Cita: Debería indexar todos los campos dónde hago "ORDER BY " ?
Dependería del impacto en tu aplicación.
Básicamente, la pregunta sería qué tan frecuente es el uso de consultas con ese tipo de ordenamientos. Si son muy esporádicas, el costo de mantenimiento de los índices podría ser antiperformántico.
Esa sería una de las claves a considerar, ya que la creación de índices sobre las tablas tiene un costo importante al momento de los INSERT y UPDATE. Si tu base tiene un alto nivel de inserciones y actualizacioens diartio, el efecto puede ser bastante malo.
En otras palabras: No es una mala idea pero hay que analizar la conveniencia caso por caso.