Heb je geprobeerd de oorspronkelijke query uit te voeren met TOP 1? hoogstwaarschijnlijk zal het net zo langzaam zijn.
Soms, wanneer de optimizer denkt dat iets zeer waarschijnlijk is en met weinig moeite een enorme set gegevens gaat retourneren (d.w.z. bijna alle records worden geretourneerd), kiest het meestal lus-joins omdat het alleen de eerste en een loop join is goed om maar een paar records te krijgen. Als dat niet waar blijkt te zijn, duurt het een eeuwigheid en een dag om resultaten te krijgen.
In jouw geval klinkt het alsof het zeer zeldzaam is, dus deze keuze doet erg pijn. Probeer in plaats daarvan iets te doen als SELECT @count = COUNT(*) FROM ... en controleer dan of die telling niet nul is.