Habría que ver que datos maneja esa consulta y revisar el plan de ejecución.
Los
LIKE no es que se an muy óptimos y dependiendo de los datos puede ser muy costoso y el
NOT IN, tampoco ayuda.
Intenta ejecutarla con un rango pequeño de datos y revisa los índices que tienes en las tablas.
Revisa que no se esté produciendo ningun bloqueo (deadlock) en la Bd mientras la ejecutas (no comentas si hay más procesos trabajando). aunque eso debería "saltar" al cabo de un rato por TimeOut/Deadlock.