Hola amigo, te comento:
La tabla T2 la usan para meter alli los servicios que contratan por dia (te lo digo, es un sauna), esto implica usar un casillero (separar un numero) y luego al cambiar de estado de A a C reusan ese numero. Vale decir que el numero o casilla se usa una sola vez por vez, pero puede usarse varias veces en el dia pq en el dia varios clientes pueden tomar en diferentes momentos esa casilla. Entonces en la tabla T2 estan metiendo todas esas transacciones.
Por ello cree la tabla nueva a manera de tabla transaccional como comentas y esto fue la solución de momento.
Efectivamente en esos campos están los indices, es mas, recompute la selectividad y fue lo mismo.
El query esta en VB6 y la BD es Firebird (por eso conseguí este cliente)
Esto me arroja el plan y el costo lo tiene la tabla que mencione T2

Aquí estoy probando con 100 registros en T1 y 45,000 en T2 y la demora es de 3 segundos y fíjate que hace muchas vueltas (5 millones de leídas) porque esta prueba la estoy haciendo con una BD de meses atras que lo único que ha cambiado en estos tiempos son la cantidad de registros.
Y lo esta tomando Natural, ya he corrido otros querys diferentes a la mismas tablas y campos y si usan los indices, quizá algo se me esta pasando aquí.

La BD se ejecuta en una PC normal con Windows 7 de 64 y con 8GB de RAM y si esta prácticamente dedicada esta PC para el uso de este sistema. Y las pruebas que yo hago las hago en una maquina virtual pero mi PC tiene 16GB de ram W7-64 y en esta maquina virtual ya he corrido consultas mas grandes sin esa lentitud.
Entonces ¿consideras que esta bien mejor usar esta tabla intermedia de manera formal o crees que se pueda mejorar el query? ya probé algo similar a esto:
SELECT T1.CAMPO1
FROM TABLA1 T1
LEFT JOIN TABLA2 T2 ON T1.CAMPO1 = T2.CAMPO1 AND
T2.CAMPO1 IS NULL
WHERE
T2.CAMPO2 = 'A'
AND T2.CAMPO3 = '2014/09/12'
Pero me da el mismo ratio de lentitud.