El count es lo mejor poniendo todo en la balanza, aparte es la manera correcta, y es de lo último que se logra de una buena normalización de datos.
El sobrecargar no te hagas problema siempre y cuando sea necesario y este bien optimizado.
Personalmente, en casos extremos, he usado hasta archivos planos/xml en conjunto de la db para optimizar la labor (ej, en el caso de noticias, donde la lectura es mayor a la escritura), creando una especie de cache interna del sistema (luego, viendo el fuente por ejemplo de mambo vi algo similar implementado ahí, eso quiere decir que tan loco no estaba :P).
En fin, es cuestión que hagas bien las consultas (sobre todos los condicionales), y manejes bien los PK, índices y demás yerbas (por eso los links;))
Obviamente esto es tan extenso que seguramente este/mos olvidando cosas, por eso, si alguien aporta será bienvenido!
PD: Léete las ventajas de mysql 4.1.3> y veras que sacas provecho de esto! (
www.mysql.com)