Como optimizar un UPDATE a pesar de tener INDICES

[LUISESPOCH]

Hola amigos todos tengo un serio problema haber si me pueden echar una mano en esto:

Tengo un SP que contiene el siguiente bloque de Update para 1 solo campo, que se esta tomando mucho tiempo. 10 millones de registros se toma más de 10 horas y no se cómo optimizarlo.

UPDATE A
SET CODIGO_USUARIO=B.CODIGO_ANTERIOR_USUARIO
FROM TABLA1 A, OTRABASEDATOS..TABLA2 B
WHERE
A.CODIGO_USUARIO_MBA=B.CODIGO_HOMOLOGADO_USUARIO
AND A.FECHA_INICIO = @FECHA_I

El campo que actualiza es un varchar(25), ejemplo "usuarioXYZ", usando como codigo de busqueda otro varchar(25) un valor como "045712"



Cuando uso sp_lock con el Id de mi proceso tengo 4891 filas que indican bloqueos de pagina. Por lo general con la siguiente informacion:

SPID
78 -->mi proceso ene ejcucion
DBID
15 --> mibd
OBJID
1518784618 ??
IndId
0
Type
PAG
Resource
5:20496537
Mode
X
Status
GRAND



He creado indices para cada tabla utilizando como campos las columnas del WHERE para cada tabla. Osea en todas 2 indices:

INDICE PARA TABLA1:
IDX_FILTRO_COMUN (CODIGO_USUARIO_MBA, FECHA_INICIO)

INDICE PARA TABLA2:
IDX_FILTRO_COMUN (CODIGO_HOMOLOGADO_USUARIO)


He procedido incluso a bajar la data de la tabla 2 que proviene de otra BD y ponerla en una tabla de la misma BD de la tabla 1, pero no percibo ventaja alguna.

Trabajo con SQLServer 2000

Por favor si alguien me da una sugerencia al respecto, le quedare agradecido.

Gracias a tod@s por la ayuda

LE