Sachverhalt:
A. Die Baubehörde Zollikon erteilte Y._ am 14. Mai 2007 die baurechtliche Bewilligung für den Neubau eines Wohn- und Geschäftshauses auf dem Grundstück Kat.-Nr. 10'404 an der Dufourstrasse 8 in Zollikon. Gleichzeitig eröffnete sie der Bauherrin die Ausnahmebewilligung der Baudirektion Zürich vom 3. Mai 2007 für die Zufahrt zur Unterniveau-Garage über die Freihaltezone. Das Projekt sieht seeseitig die Zufahrt von der parallel zur Bahnlinie Zürich-Rapperswil verlaufenden Seefeldstrasse zur unterirdischen Tiefgarage mit insgesamt 10 Parkplätzen vor. Diese Erschliessung führt über einen der kommunalen Freihaltezone zugewiesenen Streifen von ca. 5 m Breite. Zwei Besucherparkplätze sind bergseitig auf dem höher gelegenen Teil des Baugrundstücks längs der Dufourstrasse angelegt.
Bereits zuvor war das Vorhaben Gegenstand verschiedener vom Nachbarn X._ angestrengter Rechtsmittelverfahren gewesen. U.a. hatte das Bundesgericht mit Urteil 1A.49/2006 vom 19. Juli 2006 die damaligen Bau- und Ausnahmebewilligungen aufgehoben und die Angelegenheit an das Verwaltungsgericht des Kantons Zürich zurückgewiesen. Das Bundesgericht hatte erwogen, eine Standortgebundenheit für die Erschliessung über die Freihaltezone sei nicht gegeben, weshalb die Ausnahmebewilligung zu Unrecht erteilt worden sei. Bislang sei nicht geprüft worden, ob allenfalls die Möglichkeit bestehe, die Garagenzufahrt gestützt auf Art. 24c RPG als teilweise Änderung oder massvolle Erweiterung der in diesem Bereich bestehenden Parkfelder zu bewilligen. Da sich aber bis anhin keine Behörde zu dieser Problematik geäussert habe, sei es nicht Sache des Bundesgerichts, darüber in erster Instanz zu befinden. In seinem neuen Entscheid vom 13. September 2006 hiess das Verwaltungsgericht hierauf die Beschwerde teilweise gut und wies die Sache zur Fortsetzung des Baubewilligungsverfahrens an die Baubehörde Zollikon zurück.
B. Gegen die beiden neuen Beschlüsse der Gemeinde und des Kantons gelangte X._ am 16. Juli 2007 wiederum an die Baurekurskommission II. Die Baurekurskommission vereinigte die Verfahren und wies den Rekurs mit Entscheid vom 22. Januar 2008 ab.
C. Mit Beschwerde vom 25. Februar 2008 beantragte X._ dem Verwaltungsgericht des Kantons Zürich, die Baubewilligung der Baubehörde Zollikon vom 14. Mai 2007, die Ausnahmebewilligung der kantonalen Baudirektion vom 3. Mai 2007 sowie den Rekursentscheid vom 22. Januar 2008 aufzuheben.
Das Verwaltungsgericht wies die Beschwerde mit Urteil vom 23. April 2008 ab.
D. Am 23. Juni 2008 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des verwaltungsgerichtlichen Urteils. Gleichzeitig ersucht er um Gewährung der aufschiebenden Wirkung.
Die Bauherrin und private Beschwerdegegnerin, Y._, schliesst, genauso wie die Gemeinde Zollikon und das Verwaltungsgericht des Kantons Zürich, auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Die kantonale Baudirektion beantragt ebenfalls, die Beschwerde sei abzuweisen.
Im (zum Teil unaufgefordert erfolgten) zweiten Schriftenwechsel halten die Parteien sinngemäss an ihren Anträgen fest.
Das Bundesamt für Raumentwicklung hat sich ebenfalls zur Angelegenheit vernehmen lassen und folgt den kantonalen Behörden in ihrer Argumentation im Wesentlichen.
Die kantonalen Instanzen verzichten auf weitere Stellungnahmen, während die Parteien ihre Anträge aufrecht erhalten und sich die Gemeinde Zollikon inhaltlich zu gewissen Erwägungen des ARE äussert.
Mit Verfügung vom 21. Juli 2008 hat das präsidierende Mitglied der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt.
E. Der Beschwerdeführer hat das Bundesgericht mit Schreiben vom 15. Dezember 2008 über den Tod der privaten Beschwerdegegnerin am 29. November 2008 in Kenntnis gesetzt.
Mit Schreiben vom 30. Januar 2009 bestätigt der Vertreter der Beschwerdegegnerin, dass seitens deren Erben ein unvermindertes Interesse am Bauprojekt und an einem raschen Beschwerdeentscheid bestehe.

Erwägungen:
1. 1.1 Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Endentscheid (<ref-law>). Gestützt auf <ref-law> beurteilt das Bundesgericht Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält dazu keinen Ausschlussgrund. Gemäss Art. 34 Abs. 1 RPG in der Fassung nach Ziff. 64 des Anhangs zum Bundesgesetz vom 17. Juni 2005 über das Bundesverwaltungsgericht (VGG; SR 173.32; vgl. AS 2006 2261) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege (<ref-ruling> E. 1.2 S. 251).
1.2 Der Beschwerdeführer als Nachbar des umstrittenen Projekts ist ohne weiteres zur Beschwerde legitimiert (zur Legitimation gemäss <ref-law> siehe <ref-ruling> E. 1.3.3 S. 253 f.). Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, weshalb auf die Beschwerde unter Vorbehalt der rechtsgenüglichen Begründung (dazu E. 1.3 und 1.4 hiernach) einzutreten ist.
1.3 Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Genügt die Beschwerdeschrift diesen Begründungsanforderungen nicht, so ist darauf nicht einzutreten. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (<ref-law>); dies setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die minimalen Begründungsanforderungen von <ref-law> erfüllt.
Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung - <ref-ruling> E. 1.4.3 S. 255) geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Für derartige Rügen gelten die gleichen Begründungsanforderungen, wie sie gestützt auf Art. 90 Abs. 1 lit. b OG für die staatsrechtliche Beschwerde gegolten haben (<ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen; auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.3 S. 261 mit Hinweisen).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Soweit der Beschwerdeführer die vorinstanzlichen Sachverhaltsfeststellungen beanstandet und eine mangelhafte Sachverhaltsfeststellung für den Ausgang des Verfahrens entscheidend ist, kann er nur geltend machen, die Feststellungen seien offensichtlich unrichtig oder beruhten auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 97 Abs. 1 und <ref-law>). Eine entsprechende Rüge ist substanziiert vorzubringen (E. 1.3 hiervor). Vorbehalten bleibt die Sachverhaltsberichtigung von Amtes wegen nach <ref-law> (vgl. <ref-ruling> E. 1.4.3 S. 254 f.).
1.5 Die Beschwerdegegnerin ist inzwischen verstorben. Da ihr Bauvorhaben jedoch bewilligt wurde, ist kein Grund ersichtlich, nicht über die Beschwerde zu entscheiden. Die Erben halten ausdrücklich am streitbetroffenen Projekt fest und treten an die Stelle der Beschwerdegegnerin. Das Interesse des Beschwerdeführers an einem Entscheid über die Rechtmässigkeit der Parkplätze ist unverändert.
2. Die kantonalen Behörden haben die Bewilligung für die Zufahrt über die Freihaltezone jetzt gestützt auf den durch Art. 24c RPG vermittelten Bestandesschutz erteilt. Der Beschwerdeführer vertritt die Auffassung, die Voraussetzungen dazu seien nicht erfüllt. Er wirft den kantonalen Instanzen vorab eine offensichtlich falsche Sachverhaltsfeststellung vor.
2.1 Art. 24c Abs. 1 RPG schützt bestimmungsgemäss nutzbare, aber zonenwidrig gewordene Bauten und Anlagen ausserhalb der Bauzonen grundsätzlich in ihrem Bestand. Nach Abs. 2 der zitierten Bestimmung können solche Bauten und Anlagen teilweise geändert oder massvoll erweitert werden, sofern sie rechtmässig erstellt oder geändert worden sind; in jedem Fall bleibt die Vereinbarkeit mit den wichtigen Anliegen der Raumplanung vorbehalten. Die Zulässigkeit einer teilweisen Änderung oder massvollen Erweiterung ergibt sich unmittelbar aus dem Bundesrecht (<ref-ruling> E. 3b S. 219 mit Hinweisen). Der Bundesrat hat in Art. 41 und 42 RPV die zulässigen Änderungen im Sinne von Art. 24c Abs. 2 RPG konkretisiert. Nach <ref-law> sind Änderungen zulässig, wenn die Identität der Baute oder Anlage einschliesslich ihrer Umgebung in den wesentlichen Zügen gewahrt bleibt. Verbesserungen gestalterischer Art sind zulässig. Ob die Identität der Baute im Wesentlichen gewahrt bleibt, ist gemäss <ref-law> unter Würdigung der gesamten Umstände zu beurteilen. Sie ist jedenfalls dann nicht mehr gewahrt, wenn die zonenwidrig genutzte Fläche um mehr als 30 % erweitert wird, wobei Erweiterungen innerhalb des bestehenden Gebäudevolumens nur zur Hälfte angerechnet werden (lit. a), oder wenn die zonenwidrig genutzte Fläche innerhalb oder ausserhalb des bestehenden Gebäudevolumens um insgesamt mehr als 100 m2 erweitert wird (lit. b).
2.1 Art. 24c Abs. 1 RPG schützt bestimmungsgemäss nutzbare, aber zonenwidrig gewordene Bauten und Anlagen ausserhalb der Bauzonen grundsätzlich in ihrem Bestand. Nach Abs. 2 der zitierten Bestimmung können solche Bauten und Anlagen teilweise geändert oder massvoll erweitert werden, sofern sie rechtmässig erstellt oder geändert worden sind; in jedem Fall bleibt die Vereinbarkeit mit den wichtigen Anliegen der Raumplanung vorbehalten. Die Zulässigkeit einer teilweisen Änderung oder massvollen Erweiterung ergibt sich unmittelbar aus dem Bundesrecht (<ref-ruling> E. 3b S. 219 mit Hinweisen). Der Bundesrat hat in Art. 41 und 42 RPV die zulässigen Änderungen im Sinne von Art. 24c Abs. 2 RPG konkretisiert. Nach <ref-law> sind Änderungen zulässig, wenn die Identität der Baute oder Anlage einschliesslich ihrer Umgebung in den wesentlichen Zügen gewahrt bleibt. Verbesserungen gestalterischer Art sind zulässig. Ob die Identität der Baute im Wesentlichen gewahrt bleibt, ist gemäss <ref-law> unter Würdigung der gesamten Umstände zu beurteilen. Sie ist jedenfalls dann nicht mehr gewahrt, wenn die zonenwidrig genutzte Fläche um mehr als 30 % erweitert wird, wobei Erweiterungen innerhalb des bestehenden Gebäudevolumens nur zur Hälfte angerechnet werden (lit. a), oder wenn die zonenwidrig genutzte Fläche innerhalb oder ausserhalb des bestehenden Gebäudevolumens um insgesamt mehr als 100 m2 erweitert wird (lit. b).
2.2 2.2.1 Zunächst stellt der Beschwerdeführer in Abrede, dass die bestehenden Parkplätze rechtmässig erstellt worden seien. Der Zeitpunkt des Baus sei entgegen den Ausführungen der Vorinstanzen unbekannt und eine formelle Bewilligung sei nie erteilt worden.
2.2.2 Die Baudirektion und das Verwaltungsgericht haben auf verschiedene Akten abgestellt, um das Entstehungsdatum der Parkplätze zu eruieren. Unbestritten ist, dass keine ausdrückliche schriftliche Bewilligung für die Parkfelder vorhanden ist. Die Vorinstanzen stützen sich indes einerseits auf den Beschluss Nr. 1551 vom 26. März 1970, mit welchem der Regierungsrat des Kantons Zürich das Ausführungsprojekt für die Phase 1b des Anschlussbauwerks Tiefenbrunnen im Bereich der Gemeindegrenze Zollikon/Zürich südlich der Bahnstation Tiefenbrunnen genehmigte und den dazu erforderlichen Bruttokredit bewilligte. Dieses Projekt sah im Gebiet "Wässerig", wo das streitbetroffene Grundstück liegt, umfangreiche Bauarbeiten an der Seefeldstrasse/Dufourstrasse vor. Die Baudirektion und mit ihr das Verwaltungsgericht sind der Meinung, der zum Beschluss gehörende Ausführungsplan weise den streitigen Parkplatz mit gestrichelter Linie als befestigten Platz aus. Weiter zog die Baudirektion einen Landabtauschvertrag zwischen den SBB und dem Kanton Zürich bei. Dieser Vertrag wurde im Zusammenhang mit dem vorerwähnten Projekt nach Besitzesantritt abgeschlossen und vom Regierungsrat am 1. März 1972 genehmigt. In dem Bestandteil des Vertrags bildenden Situationsplan 1 ist nach Auffassung der kantonalen Instanzen der Parkplatz ebenfalls mittels gestrichelter Linie eingezeichnet. Schliesslich liegt den Akten ein Luftbild vom 6. Oktober 1971 bei, welches offensichtlich während den Bauarbeiten aufgenommen wurde. Das Überführungsbauwerk war zu diesem Zeitpunkt realisiert. Für das Verwaltungsgericht sind auf dem Bild im Bereich des Parkplatzes Erdarbeiten erkennbar. Die Art der Arbeiten sei allerdings nicht genau erkennbar (Parkplatz, Installationsplatz oder Ähnliches).
2.2.3 Die Einwände des Beschwerdeführers gegen diese Argumentation erachtet das Verwaltungsgericht als unbegründet: Dass im Genehmigungsbeschluss Nr. 1551 vom 26. März 1970 die Parkplätze nicht speziell erwähnt würden, besage nichts, sei doch dies ein völlig untergeordneter Bauteil gewesen. Zur Behauptung, es sei kein Motiv ersichtlich, weshalb der Kanton Parkfelder zugunsten der Öffentlichkeit hätte erstellen sollen, führt das Verwaltungsgericht aus, die Gemeinde habe darauf hingewiesen, dass diese 14 Parkplätze als Ersatz für die Parkplätze erstellt worden seien, die entlang dem seeseitigen Rand der ursprünglichen Dufourstrasse zwischen Bahnübergang und Dufourstrasse Nr. 32 bestanden hatten. Zudem sei allein bestritten, wann und nicht dass der Kanton die Parkplätze erstellt habe. Aus dem Umstand, dass der Parkplatz als völlig untergeordneter Bauteil im Technischen Bericht zum Projekt sowie im Beschluss Nr. 1861 des Regierungsrates vom 5. April 1978 zur Genehmigung der Bauabrechnung nicht erwähnt werde und auch in den Projektplänen zur Situation nicht eingezeichnet sei, könne der Beschwerdeführer nichts für sich ableiten. Nicht nachvollziehbar sei die Aussage des Beschwerdeführers, wonach die Erstellung des Parkplatzes vor und nach dem 20. März 1970 innerhalb der vorhandenen Geländetopographie gar nicht möglich gewesen sei, nachdem der Parkplatz ja heute bestehe. In diesem Zusammenhang sei zu erwähnten, dass die "1 m"-Angabe im Projektplan sich auf die Breite des Banketts beidseits der Strasse beziehe und nicht auf die Böschungshöhe. Tatsache sei, dass die Parkfläche im vom Regierungsrat genehmigten Ausführungsplan als befestigte Fläche eingezeichnet sei, und zwar als gestrichelte Linie. Diese Markierung gehöre offensichtlich nicht zur Geländelinie, wie der Beschwerdeführer behaupte, sondern begrenze die Parkfläche genauso wie die nordwestlich anschliessenden Gehweganlagen. Die gleiche gestrichelte Linie als Begrenzung der befestigten Fläche sei auch in den vom Beschwerdeführer eingereichten Katasterkopien von 1988 und 1992 eingetragen. Auch im Beilageplan zum Tauschvertrag sei die befestigte Fläche - hier mit durchgehendem Strich - verzeichnet. Dass im Laufe der Bauarbeiten von der Situierung gemäss den Plänen leicht abgewichen worden sei, sei nichts Ungewöhnliches. Der Luftaufnahmeplan vom 6. Oktober 1971 belege Erdarbeiten, auch wenn diese nicht genau zugeordnet werden könnten. Mindestens in ihren Umrissen entspreche die Fläche neben der Gehweganlage dem Parkplatz. All diese planerischen Darstellungen stützen nach Meinung des Verwaltungsgerichts die Aussagen der Gemeinde Zollikon und der Baudirektion, wonach die Parkfläche 1970/71 vom Kanton erstellt worden sei, dies als Teil des grossen Überführungs- und Kreuzungsbauwerks im Bereich der Dufour-, Seefeld- und Dammstrasse und als Ersatz für aufgehobene Parkplätze. Insgesamt sprächen gewichtige Indizien dafür, dass die Parkierungsanlage bereits 1970/71 erstellt worden sei.
2.2.4 Die Würdigung der Aktenlage durch die Vorinstanzen ist nicht zu beanstanden. Mit seinen dagegen gerichteten Rügen dringt der Beschwerdeführer nicht durch, widerlegen seine Vorbehalte doch die Schlussfolgerungen des Verwaltungsgerichts nicht in rechtsgenüglicher Weise (vgl. E. 1.3 und 1.4 hiervor). Die im Ausführungsplan zum Genehmigungsbeschluss Nr. 1551 vom 26. März 1970 eingezeichnete gestrichelte Fläche kann im östlichen Bereich nicht den Gehweg darstellen, würde doch letzterer sonst unvermittelt sozusagen im "Nichts", respektive abrupt auf Höhe des Hauses des Beschwerdeführers enden. Zudem ist nicht ersichtlich, wozu diese über 30 m lange und 5 m tiefe Fläche sonst dienen sollte. Deutlicher wird die Parkfläche in dem zum Tauschvertrag zwischen Kanton und SBB (vom Regierungsrat am 1. März 1972 genehmigt) gehörenden Plan 1:500 hervorgehoben: Hier ist die Umgrenzungslinie klar erkennbar durchgezogen. Keinen Grund, die Sachverhaltsfeststellung des Verwaltungsgerichts per se als falsch erscheinen zu lassen, stellt der Umstand dar, dass die Parkplätze im Regierungsratsbeschluss Nr. 1551 nicht explizit erwähnt werden. Im Zusammenhang mit dem ganzen Strassenprojekt waren sie von untergeordneter Bedeutung. Immerhin ist das Parkfeld im Ausführungsplan von derselben gestrichelten Linie umfasst wie der Gehweg und damit offensichtlich als befestigte Fläche markiert.
2.2.5 Hätten die vom Beschwerdeführer behaupteten baulichen Hindernisse im Gelände bestanden, wären auch heute keine Parkplätze vorhanden. Zudem lässt sich auf dem Luftbild vom 6. Oktober 1971 erkennen, dass im fraglichen Bereich Erdarbeiten vorgenommen werden oder wurden. Auch darin ist dem Verwaltungsgericht zuzustimmen. Soweit sich der Beschwerdeführer auf den am 12. Mai 2004 revidierten Plan "Umgebung" (Beilage Nr. 10 des Beschwerdeführers) beruft und geltend macht, die darin enthaltene gestrichelte gelbe Linie entspreche nicht den bestehenden Parkfeldern, sondern stelle eine "Bodenbedeckungslinie" dar, kann auf den Projektplan "Zufahrt" vom 8. November 2006 verwiesen werden (Akten BRK II Nr. 18.7). In diesem werden die beanspruchte Fläche von 1.7 m2 für die Zufahrt und die als Kompensation vorgesehene neue Grünfläche von 21.5 m2 aufgezeigt. Darin ist das der erwähnten gestrichelten Fläche entsprechende Areal ebenfalls ausgewiesen, diesmal ausdrücklich als "14 bestehende Parkplätze Gemeinde" - und korrespondiert wiederum mit der gestrichelten Linie im Ausführungsplan zum Regierungsratsbeschluss Nr. 1551. Im Plan, auf den sich der Beschwerdeführer bezieht, sind zudem nur 11 Parkplätze als bestehend vermerkt. Es handelt sich bei dem rot umrandeten Feld darum nicht um die heute vorhandenen Parkplätze, sondern um eine allenfalls künftige Parkplatzanordnung.
2.2.6 Die Vorhalte des Beschwerdeführers beruhen auf Vermutungen und Behauptungen. Es genügt aber nicht, wenn er die Ausführungen der Vorinstanzen grundsätzlich und umfassend bestreitet, ohne deren angebliche Unrichtigkeit durch gewichtige Indizien zu belegen. Die Sachverhaltsermittlung der Vorinstanzen ist jedenfalls nicht offensichtlich falsch.
2.2.7 Offen bleiben kann darum, ob das von der Beschwerdegegnerschaft erst vor Bundesgericht eingereichte Luftbild vom 10. August 1972 ein unzulässiges Novum darstellt, da der von der Baudirektion und dem Verwaltungsgericht eruierte Sachverhalt auch ohne dieses Foto als nachvollziehbar erscheint.
2.3 Der Anwendungsbereich von Art. 24c RPG ist auf Bauten und Anlagen beschränkt, die nicht mehr zonenkonform, d.h. durch eine nachträgliche Änderung von Erlassen oder Plänen zonenwidrig geworden sind (<ref-law>; vgl. <ref-ruling> E. 2c). Die Bestandesgarantie nach Art. 24c RPG erstreckt sich damit nur auf Bauten, die seinerzeit in Übereinstimmung mit dem materiellen Recht erstellt und aufgrund einer späteren Rechtsänderung zonenwidrig geworden sind, nicht aber auf Bauten, bei denen die Zonenwidrigkeit ohne Rechtsänderung, sondern allein durch tatsächliche Änderungen, wie namentlich die Aufgabe des Landwirtschaftsbetriebes, entstanden ist (PETER KARLEN, Die Ausnahmebewilligung nach Art. 24-24d RPG, System der neuen Regelung, in: ZBl 102/2001 S. 291, 296 f.). "Seinerzeit" erstellte Bauten und Anlagen sind in erster Linie solche, die vor dem 1. Juli 1972 erstellt wurden, d.h. vor dem Inkrafttreten des Bundesgesetzes vom 8. Oktober 1971 über den Schutz der Gewässer gegen Verunreinigung (aGSchG; AS 1972 950). Mit diesem Gesetz wurde erstmals eine klare Trennung von Bau- und Nichtbaugebiet vorgenommen (BUNDESAMT FÜR Raumentwicklung, Neues Raumplanungsrecht, Erläuterungen zur Raumplanungsverordnung und Empfehlungen für den Vollzug, Bern 2000, S. 43 f.; a.A. KARLEN, a.a.O., S. 297 f.). Nach dem 1. Juli 1972 erstellte Bauten und Anlagen fallen namentlich dann in den Anwendungsbereich von Art. 24c RPG, wenn sie aufgrund einer Zonenplanänderung von der Bauzone in eine Nichtbauzone gelangten (<ref-ruling> E. 4.2.1 S. 398 f. mit Hinweisen).
2.3.1 Das Verwaltungsgericht zieht dazu im angefochtenen Entscheid in Erwägung, auf kantonaler Stufe habe vor dem 1. Juli 1978, an welchem § 309 lit. i des Planungs- und Baugesetzes vom 7. September 1975 (PBG/ZH) in Kraft trat, keine Bewilligungspflicht für Parkplätze bestanden. Das Baugesetz für Ortschaften mit städtischen Verhältnissen vom 23. April 1893, welches mit dem Inkrafttreten des PBG/ZH formell aufgehoben wurde, habe in § 125 nur eine Baubewilligungspflicht für Bauten, nicht für Anlagen statuiert. Ob auf Bundesebene bereits mit dem Inkraftreten des Gewässerschutzgesetzes eine Bewilligungspflicht für Parkplätze innerhalb der Bauzone eingeführt worden sei, könne offen bleiben. Selbst wenn die Anlage im Zeitpunkt ihrer Erstellung einer Bewilligung bedurft hätte, schliesse dies die Anwendung von Art. 24c RPG nicht aus. In diesem Fall sei zu prüfen, ob die Rechtswidrigkeit bloss formaler oder auch materieller Natur sei. Eine formell illegale Baute oder Anlage sei nachträglich zu bewilligen, wenn sie im Zeitpunkt der Erstellung dem materiellen Recht entsprochen habe. Demgemäss sei in erster Linie abzuklären, ob die Parkplatzanlage seinerzeit in Übereinstimmung mit dem materiellen Recht erstellt worden und durch die Zonenplanänderung von 1985/1988 zonenwidrig geworden seien.
2.3.2 Zu dieser Problematik führt das Verwaltungsgericht aus, gemäss dem vom Regierungsrat am 7. November 1963 bzw. 11. November 1965 genehmigten Zonenplan sei das streitbetroffene Gebiet der Wohnzone zugewiesen gewesen. Erst mit der Zonenplangenehmigung vom 18. September 1985/7. September 1988 sei das Gebiet entlang der Seefeldstrasse in die Freihaltezone gekommen. Die Baudirektion habe in der Bewilligung vom 3. Mai 2007 festgehalten, der Parkplatz habe bei der Umzonung 1985/88 bereits bestanden. Konkrete Anhaltspunkte, die gegen diese Aussage sprechen würden, habe der Beschwerdeführer nicht genannt und seien auch nicht ersichtlich. Selbst wenn darum anzunehmen wäre, dass die Parkierungsanlage trotz der dafür sprechenden Indizien nicht bereits 1970/71 erstellt worden wäre, sei davon auszugehen, dass sie jedenfalls vor der massgeblichen Umzonung bereits bestanden habe. Bis zum Zeitpunkt der Umzonung gemäss der Zonenplanung von 1985/88 seien die Parkplätze bewilligungsfähig gewesen. Somit seien sie seinerzeit in Übereinstimmung mit dem materiellen Recht erstellt worden und erst durch die Zonenplanänderung von 1985/88 zonenwidrig geworden.
2.3.3 Der Beschwerdeführer gesteht zu, dass das Parkfeld wohl vor dem 7. September 1988 erstellt worden sei (Ziff. 3.2 der Beschwerdeschrift, in fine). Er vertritt indes die Auffassung, es habe den materiellen Bauvorschriften nicht genügt, da die Abwässer des Parkfeldes hätten erfasst und abgeleitet werden müssen. Hinzu komme, dass die Parkplätze schon im Jahr 1970 höchstens 4 m tief hätten sein können und auch heute bloss 5 m tief seien. Damit stehe fest, dass die Parkplätze die in § 266 PBG/ZH erforderliche Mindesttiefe von 5.50 m nie erreicht hätten. Demzufolge seien sie zu keinem Zeitpunkt bewilligungsfähig gewesen.
2.3.4 Diese Ausführungen vermögen die Feststellungen des Verwaltungsgerichts nicht als offensichtlich unrichtig zu qualifizieren. Es sind keine Hinweise für eine mangelhafte Entwässerung vorhanden, zumal die Parkplätze offenkundig bis heute keinen Anlass zu Beanstandungen gegeben haben. Weshalb die Parkplätze vor der massgeblichen Zoneplanänderung nicht bewilligungsfähig hätten sein sollen, ist nicht ersichtlich. Massgeblich ist aber, dass aufgrund des Ausführungsplanes zum RRB Nr. 1551 vom 26. März 1970 wie gesehen davon auszugehen ist, dass die Parkplätze im Zusammenhang mit dem damaligen Anschlussbauwerk erstellt wurden, mithin vor einer eigentlichen Bewilligungspflicht. Gegenteilige Anhaltspunkte liegen nicht vor.
2.4 Sodann hat das Verwaltungsgericht auch die Voraussetzungen von <ref-law> als erfüllt erachtet, dies zu Recht: Bei der Prüfung, ob die Identität der Anlage durch die teilweise Änderung noch gewahrt bleibt, haben die Vorinstanzen die Gesamtanlage als Referenzgrösse genommen, was zulässig ist (vgl. dazu BUNDESAMT FÜR RAUMENTWICKLUNG, Neues Raumplanungsrecht, Bewilligungen nach Art. 24c RPG: Änderungen an zonenwidrig gewordenen Bauten und Anlagen, Bern 2001, Ziff. 3.1 S. 8). Von den heute 14 Parkplätzen bleiben noch deren 11 bestehen. Zwar benötigt die neue Garagenzufahrt zusätzlich 1.7 m2 des heute unbefestigten Teils in der Freihaltezone. Eine Teilfläche von 21.5 m2 der bestehenden Anlage wird aber im Sinne einer zulässigen gestalterischen Verbesserung neu begrünt, so dass ingesamt keine Erweiterung der zonenwidrigen Nutzung stattfindet. Selbst wenn die neu in der Freihaltezone geschaffene Fläche nicht mehr dem ruhenden Verkehr, sondern der Zufahrt zu einer weiteren Parkfläche dient, bleibt die Identität der Anlage jedenfalls gesamthaft erhalten. Hinzu kommt, dass die Tiefgarage lediglich Platz für 10 Privatparkplätze bietet, welch letztere selber nicht in der Freihaltezone liegen. Die durch die Zufahrt bedingten Mehrimmissionen in der Freihaltezone sind darum nicht von einem Ausmass, welches den Rahmen von <ref-law> sprengen würde. Die Wesensgleichheit bleibt gewahrt. Davon geht das ARE in seiner Stellungnahme ebenfalls aus.
2.5 Mit dem ARE ist allerdings darauf hinzuweisen, dass die gemäss Art. 24c Abs. 2 RPG zulässigen Änderungs- bzw. Erweiterungsmöglichkeiten für die Gesamtanlage damit ausgeschöpft sind. Dieser Hinweis ist insofern von Bedeutung, als ein Teil der heute bestehenden Parkplätze im Eigentum der Gemeinde steht. Die Gemeinde hat denn in ihrer Stellungnahme ans Bundesgericht auch zum Ausdruck gebracht, dass sie sich dieser Rechtslage bewusst sei und insbesondere Vergrösserungen der Parkplätze oder die Erschliessung weiterer Häuser an der Dufourstrasse über die Parkplätze an der Seefeldstrasse nicht geplant oder erwünscht seien.
2.6 Insgesamt durfte das Verwaltungsgericht die Voraussetzungen von Art. 24c RPG i.V.m. Art. 41 und 42 RPV als gegeben erachten und die auf den Bestandesschutz gegründete Ausnahmebewilligung der Baudirektion schützen.
3. Daraus ergibt sich, dass die Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang hat der Beschwerdeführer die bundesgerichtlichen Kosten zu tragen (<ref-law>). Zudem hat er die Beschwerdegegnerschaft für das Verfahren vor Bundesgericht angemessen zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Erben der Y._ für das Verfahren vor Bundesgericht mit Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Baubehörde Zollikon, der Baudirektion und dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, 1. Kammer, sowie dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 6. Februar 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Scherrer