NICHT-Verknüpfung in MySQL

Eigentlich hört es sich nach einer einfachen Suche an aber MySQL weigert sich konsequent, ein stimmiges Ergebnis zu liefern.
Das Problem ist folgendes. In einer Tabelle werden Daten vom Fahrzeug gespeichert, in der anderen die Rechnungsnummern mit der dazugehörenden Fahrzeugnummmer. Nun soll eine Abfrage die Daten der Fahrzeuge ausgeben, die schon bezahlt sind, aber noch keine Rechnung erstellt wurde. (Hört sich merkwürdig an, ist aber tatsächlich so) Dieses Datum ist in der Fahrzeugtabelle gespeichert.

Meine bisherigen Überlegungen brachten diese Abfrage zustande, die aber nur leere Ergebnisse bringt.

SELECT kfz. * 
FROM kfz
WHERE zahleingang !=  '0000-00-00'
AND geloescht =  '0'
AND NOT 
EXISTS (


SELECT rechnr.rechnr
FROM kfz, rechnr
WHERE kfz.kfznr = rechnr.kfznr
AND storno =0
)

Natürlich könnnte man das in zwei getrennten Schritten machen, doch möchte ich mir das gerne sparen und meinem Verständnis nach sollte das doch auch machbar sein. Kann mir jemand auf die Sprünge helfen, wo der Fehler liegt oder einen anderen Lösungsweg aufzeigen?
Danke schonmal im Voraus.

Ich habe vor ein paar Tagen durch Zufall bei der Suche zu einem anderen Problem eine Lösung dazu in einer MySQL Dokumentation gefunden. Durch ein recht marodes Netz hier bei mir hatte ich bis jetzt noch keine Möglichkeit, sie zu posten.

SELECT kfz.*
FROM kfz
LEFT JOIN rechnr ON kfz.kfznr = rechnr.kfznr
WHERE zahleingang != '0000-00-00' 
and geloescht = '0'
and rechnr.kfznr IS NULL