Select Count (0) ... ¡¡Lento y falso!!

Hola, me encuentro ejecutando una instruccion que me devuelva el total de
filas existente en una tabla x, para lo cual utilizo el Select count(0) As
TotFilas from MiTabla, el problema es que tarda demasiado en devolverme
dicho
valor. Cabe mencionar que este proceso lo hago a través de mas de 500
servidores (con 24 tablas por cada servidor) en diferentes localidades de
mi
país, y solo aproximadamente el 1 porciento de los casos se presenta esta
situación (160 diferentes tablas de diversas localidades), lo peor es que
en
muchas ocasiones la instrucción me devuelve CERO registros, que es falso
ya
que tras varios intentos, me regresa ya una cifra real. Esto no es todo el
universo, por lo cual sospecho que debe haber algun problema con los
índices
de las tablas involucradas, pero en sí no estoy seguro de como funciona
internamente un Select count(0) como para poder encontrar una solucion
elegante a mi problema.

Saludos