Borrado extremadamente lento

Hola:
Necesito un poco de ayuda. Trato de explicar la situación. Tengo una
tabla TA con su clave primaria compuesta de un sólo campo A y una tabla TB
con su clave primaria compuesta de un sólo campo B. Con estas dos tablas
implemento una relación muchos a muchos en una tabla TAB con clave primaria
en los campos A y B que a su vez son clave ajena de las tablas TA y TB
respectivamente. Además tengo 15 tablas con los campos A y B formando clave
ajena contra la tabla TAB. Hasta aquí nada del otro mundo.
Mi problema viene al intentar borrar registros de la tabla TAB de la
forma "delete from TAB where A=@valor" ya que tarda una eternidad. El
problema es evidentemente la integridad referencial ya que si antes del
borrado deshabilito las relaciones de todas la tablas con la tabla TAB
entonces el borrado es casi inmediato. Esto no es solución ya que en el
periodo que están deshabilitadas las relaciones podrían entrar datos
incoherentes. LA tabla TAB tiene 5 millones y medio de registros y las otras
15 tienen un media de casi el millón de registros.
Por favor, ¿me podéis echar una mano para poder resolver esto? No sé
por donde tratar de buscar la solución.
Gracias de antemano y perdón por el tostón de explicación pero creo que
era necesario.

Jesús Corbí.