SQL Server - Error en Indices

Hola a todos los foristas, mi consulta es la siguiente:
Tengo una tabla de aproximendamente 3 millones de registros a la que se le realiza una consulta muy frecuentemente, 300/400 veces al día entre rangos de fechas, con el siguiente Where:

Select ID, idCliente, Fecha, etc... from Ordenes
Where FHOrden>= :xFechaIni and FHOrden< Dateadd(dd,1, :xFechaFin)

El campo fecha (FHOrden) es de tipo DateTime, se le creo un indices a la tabla por ese campo con 90% de llenado, ese campo solo se llena con la fecha hora de la creación (insert), osea, que no se actualiza con lo update
Mi problema es que por lo menos 1 vez a la semana tengo que borrarlo y volverlo a crear, porque la consulta se demora demasiado (>1 minuto), al crearlo de nuevo la consulta se hace en 2 o 3 seg.
Tengo un plan semanal de indices y sin embargo no resuelvo esto.
Que puede estar pasando?

Gracias de antemano a quien me pueda orientar :(

PD. se me olvido decir:
SO: Windows 2003 sp2
DB: SQL 2000 sp4

Gracias

Carlos

Que signifcan los dos puntos y la x????

Es una mala idea crear un INDICE sobre una columna que sufre MODIFICACIONES, de no poder remediar esto, deberias ejecutar DIARIO un sp_updatestats y dbcc dbreindex

Hola Isaias, en lenguaje de programación Delphi es para pasar la una variable, sería enl equivalente de en ves de colocar :xFecha, coloco '31/01/2008'.
Uno de los campos indices (que es el que me esta dando problemas) es el de tipo DateTime, es recomendable separar la Fecha de la Hora, adicional te comento que corri sp_updatestats y se resolvio el problema.
Con respecto a la observación sobre hacer un indice sobre una columna que sufre modificaciones, no es buena idea, pero mi pregunta seria si existe alguna otra manera de poder realizar una consulta eficiente por el campo DateTime sin indice?
Gracias por tus respuestas Isaias.....

Bueno, esa pregunta (SIN INDICES) se responde sola, ya que es como querer buscar al "Dr. John Smith" en el Empire State, sin tener un directorio en la entrada.