Also irgendwie muss es an den Daten liegen, aber das kann ich von hier aus nicht beurteilen.

Mir fällt aber auch sonst nichts mehr ein, woran es noch liegen könnte.

Aber das könntest Du noch mal testen
was aber eigentlich durch den Inner join abgedeckt war. Aber probieren geht über studieren ;-)

SELECT * FROM TCNSHD a
left join TSTATS b on a.SP=b.SP and a.CNSNOSP=b.CNSNOSP
where
B.STATUSCODE = '116' and
A.finalflag= 0
AND NOT EXISTS (
SELECT *
FROM TSTATS C
WHERE COALESCE(B.FKCNS, 0) = C.FKCNS
AND C.STATUSCODE = '117')

Xanas