Oh... das wäre mir neu.. warum sollten die zurückgezogen sein?
Einige hundert Gutachten sind damals den Bach runtergegangen.
Seit 1.1.2005 (oder so) müssen Gutachten ganz bestimmte schon formelle Ansprüche genügen, also Hersteller muss eine zertifizierte Produktion haben, bestimmte Werte (Lautstärke und glaube auch Abgas) müssen im Gutachten genannt sein, zumindest erwähnt, dass keine Verschlechterung eintritt, ...
Gab es "früher" alles nicht und haben dementsprechend "alte" Gutachten auch nicht und weil sie es nicht haben, waren es dann ab 1.1.05 keine gültigen Gutachten mehr.
Die Hersteller haben dann eben rein kostenmäßig überlegt, ob für derartige alte Filter (und damit auch alte Fahrzeuge) überhaupt noch genügend Kunden sich finden, die dann auch den Preis für das neue Gutachten (per Umlage auf den Filterpreis, immerhin 4 stellige Prüfkosten je Filter, Fahrzeug, Motorisierung) und dementsprechend entschieden für viele Filter keine neuen Gutachten zu erstellen, weil das Geld über die wenig verkauften Filter für alte Fahrzeuge nicht mehr reinkommt.
Hindert allerdings nicht unbedingt daran, dass einige Verkäufer immer noch Filter mit den alten, nicht mehr gültigen Gutachten zu verkaufen. Passt der Prüfer auf, dann erlebt man mit dem Gutachten bei der Eintragung eine böse Überraschung.
Und das scheint mir hier bei Deinem Problem ("altes" Fahrzeug und K&N-Filter mit bemängeltem Gutachten) wohl der Grund zu sein.
Schaue doch mal auf der Webseite von K&N, da steht einiges darüber und auch eine Liste für aktuelle Gutachten. Ist Dein Filter oder Wagen nicht mit bei, dann war es das leider.