Sachverhalt:
A. Seit 1. Januar 1997 betreibt die Swisscom Mobile AG (heute: Swisscom (Schweiz) AG; im Folgenden: Swisscom) an der Langackerstrasse 45 in Uitikon in der Landwirtschaftszone einen Antennenstandort UITN mit mehreren GSM-900-Antennen zur Versorgung der Region Uitikon Waldegg. Am 29. Januar 2001 wurde der TDC Switzerland AG (heute: Sunrise Communications AG; im Folgenden: Sunrise) ebenfalls die Bewilligung zum Betrieb einer GSM- 900-Antennenanlage am selben Ort erteilt. Die Antennen befinden sich auf dem Dach einer Scheune; diejenigen der Sunrise sind von einer kaminähnlichen Verschalung umgeben. Die Geräteräume sind im Innern des Gebäudes untergebracht.
B. Am 23. Mai 2005 erteilte der Gemeinderat Uitikon der Swisscom und der Sunrise die baurechtliche Bewilligung für Umbau und Erweiterung der bestehenden Anlage für den Betrieb eines kombinierten GSM- und UMTS-Mobilfunknetzes. Zuvor hatte bereits die Baudirektion des Kantons Zürich am 14. April 2005 eine Ausnahmebewilligung nach Art. 24 RPG (SR 700) verfügt.
C. Gegen die erteilte Bau- bzw. Ausnahmebewilligung erhoben A.X._ und B.X._ am 2. Juli 2005 Rekurs beim Regierungsrat des Kantons Zürich. Dieser wies den Rekurs am 4. April 2007 ab.
D. Gegen den regierungsrätlichen Entscheid gelangten A.X._ und B.X._ am 19. Mai 2007 mit Beschwerde an das Verwaltungsgericht des Kantons Zürich. Dieses wies die Beschwerde am 25. Oktober 2007 ab, soweit es darauf eintrat.
E. Dagegen haben A.X._ und B.X._ am 7. Januar 2008 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Ausnahmebewilligung nach Art. 24 RPG für die Erstellung der neuen kombinierten GSM/UMTS-Mobilfunkantennen in der Landwirtschaftszone sei nicht zu erteilen.
F. Die privaten Beschwerdegegnerinnen und das Verwaltungsgericht beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Auch die Baudirektion und - im Auftrag des Regierungsrates - die Staatskanzlei des Kantons Zürich sowie der Gemeinderat Uitikon schliessen auf Beschwerdeabweisung.
G. Das Bundesamt für Raumentwicklung (ARE) äussert sich in seiner Vernehmlassung zur Standortgebundenheit der umstrittenen Anlage. Für den Fall, dass das Bundesgericht die Bewilligung grundsätzlich bestätige, beantragt es die Aufnahme einer Resolutivbedingung, wonach die Bewilligung dahinfalle, wenn die Bewilligungsvoraussetzungen nicht mehr erfüllt seien, insbesondere wenn im Abdeckungsgebiet der bewilligten Anlage aus Kapazitätsgründen eine weitere Antennenanlage notwendig werde.
Die Beschwerdeführer und die privaten Beschwerdegegnerinnen haben zur Vernehmlassung des ARE Stellung genommen.
H. Das Bundesamt für Umwelt (BAFU) kritisiert, dass das Standortdatenblatt vom 10. Juni 2004 widersprüchliche Angaben enthalte. Aufgrund dieser Widersprüche habe die Vorinstanz nicht abschliessend beurteilen können, ob die strittige Mobilfunkanlage auch nach ihrer Erweiterung die Anforderungen der NISV erfülle.
Die Baudirektion räumt in ihrer Stellungnahme ein, dass formale Unstimmigkeiten zwischen Standortdatenblatt und Baueingabeplan bestehen; diese seien bei der Prüfung des Projekts im September 2004 übersehen worden. Diese Fehler wirkten sich jedoch auf die Genehmigungsfähigkeit des Projekts nicht aus, weil der Anlagegrenzwert an den Orten mit empfindlicher Nutzung in jedem Fall eingehalten sei.
Das Verwaltungsgericht beantragt, soweit die gerügten Widersprüche Modifikationen an seinem Urteil als unumgänglich erscheinen lasse, möge das Bundesgericht einen reformatorischen Entscheid fällen.
I. Die Beschwerdegegnerinnen reichten am 8. Oktober 2008 ein neues korrigiertes Standortdatenblatt ein (datiert 15. September 2008). Sie beantragen, dieses sei als Sachverhaltsergänzung i.S.v. <ref-law> zuzulassen und auflageweise zu sanktionieren.
Das neue Standortdatenblatt wurde den Beschwerdeführern und dem BAFU zur Stellungnahme übermittelt. Am 20. Januar 2009 teilte das BAFU mit, dass die von ihm festgestellten Unklarheiten nunmehr behoben seien. Der für den Ausbau massgebende Anlagegrenzwert von 5 V/m sei an allen Orten mit empfindlicher Nutzung eingehalten. Die gegen die Baubewilligung erhobenen Einwände seien daher, was den Bereich des Schutzes vor nichtionisierender Strahlung angehe, unbegründet.
Die Beschwerdeführer betonen, Gegenstand ihrer Beschwerde sei die Ausnahmebewilligung nach Art. 24 RPG und die damit verbundenen raumplanerischen Fragen. In diesem Zusammenhang komme ein reformatorischer Entscheid des Bundesgerichts nicht in Frage.

Erwägungen:
1. Gegen das Urteil des Verwaltungsgerichts, das eine Ausnahmebewilligung für die Errichtung von Mobilfunkantennen ausserhalb der Bauzone gemäss Art. 24 RPG kantonal letztinstanzlich bestätigt, steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen. Da alle Sachurteilsvoraussetzungen vorliegen, ist auf die Beschwerde grundsätzlich einzutreten.
2. Nicht einzutreten ist allerdings auf die Rüge der Beschwerdeführer, das Bauvorhaben sei nicht korrekt bekannt gemacht worden, weil im Amtsblatt vom 4. November 2004 nur die Swisscom als Gesuchstellerin genannt worden sei.
Diese Rüge betrifft die Anwendung von kantonalem Recht (§ 314 des Zürcher Planungs- und Baugesetzes vom 7. September 1975 [PBG]). Die Verletzung von Grundrechten - einschliesslich die willkürliche Anwendung von kantonalem Recht - wird vom Bundesgericht nicht von Amtes wegen geprüft, 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).
Diesen Anforderungen genügt die Beschwerdeschrift nicht: Sie wiederholt im Wesentlichen die Rechtsauffassung der Beschwerdeführer und legt nicht (genügend) dar, inwiefern die davon abweichende Auffassung von Regierungsrat und Verwaltungsgericht das Willkürverbot verletzt.
3. Es ist unstreitig, dass der vorgesehene Umbau und die geplante Erweiterung der bestehenden Mobilfunkanlage einer Ausnahmebewilligung nach Art. 24 RPG bedarf. Umstritten ist, ob die Bewilligungsvoraussetzungen vorliegen, insbesondere ob die Anlage standortgebunden ist (Art. 24 lit. a RPG).
3.1 Das Verwaltungsgericht war der Auffassung, die streitige Anlage sei standortgebunden. Einmal falle vorteilhaft ins Gewicht, dass mit lediglich einem Antennenstandort das weitläufige und topographisch anspruchsvolle Gebiet der zweigeteilten Gemeinde Uitikon-Waldegg vollständig und gleichzeitig von zwei Mobilfunkbetreibern mit UMTS-Technologie versorgt werden könne. Zudem handle es sich um eine bereits bestehende Anlage, so dass keine neuen Anlagen an einem neuen Standort gebaut werden müssten. Ausserdem fielen die installierten Antennen gegen aussen kaum auf, und ordneten sich gut in die Umgebung ein, nachdem sie auf einer bereits bestehenden Baute angebracht und teilweise zusätzlich verschalt würden. Die geprüften Antennenstandorte in der Bauzone und die übrigen bestehenden Antennenstandort hätten sich alle als ungeeignet erwiesen; die bei deren Nutzung anfallenden Versorgungslücken könnten nur mittels zusätzlicher Antennenanlagen in der Gemeinde geschlossen werden. Insofern erscheine der ausserhalb der Bauzone erzielbare Abdeckungsvorteil derart wichtig, dass er den vorgesehenen Standort gegenüber den geprüften Alternativstandorten als viel vorteilhafter erscheinen lasse.
3.2 Die Beschwerdeführer bestreiten die Standortgebundenheit der Anlage. Aus der Vernehmlassung des Gemeinderats Uitikon an den Regierungsrat vom 2. Juli 2005 gehe hervor, dass nur deshalb keine Mobilfunkantennenanlagen innerhalb der Bauzone bewilligt worden seien, weil niemand solche Anlagen auf dem eigenen Grundstück wolle. Die Tatsache, dass vom streitigen Standort aus beide Gemeindeteile (Uitikon und Waldegg) abgedeckt werden können, genüge nach der bundesgerichtlichen Rechtsprechung nicht zur Begründung der Standortgebundenheit. Vielmehr komme die Errichtung einer Anlage ausserhalb der Bauzone erst in Betracht, wenn eine Deckungs- oder Kapazitätslücke mit einem oder mehreren Standorten innerhalb der Bauzone nicht in genügender Weise beseitigt werden könne. Es sei davon auszugehen, dass es im Wohngebiet oder in der Zone für öffentliche Bauten, bei der Allmend, oder bei der Hochspannungsleitung alternative Antennenstandorte innerhalb der Bauzone gebe.
Im Übrigen bestreiten die Beschwerdeführer das Bedürfnis für eine Erweiterung der bestehenden Mobilfunkanlage, weil die Abdeckung mit GSM- und UMTS-Mobilfunk in der Gemeinde gewährleistet sei.
3.3 Das ARE regt an, den in der Bauzone am Ostrand des Dorfteils Uitikon befindlichen Mast der Hochspannungsleitung als Alternativstandort zu prüfen.
Ansonsten räumt das ARE ein, dass der gewählte Standort Vorteile aufweise: Die Antennen überragen das Gebäude nicht bzw. nur minimal, und es seien insgesamt weniger Zellen notwendig, als wenn die Anlage in der Bauzone errichtet würde. Allerdings sei fraglich, ob dieser Vorteil von Dauer sein werde: Wie das Verwaltungsgericht ausgeführt habe, sei ein relativ engmaschiges Netz erforderlich, um die Vorteile der UMTS-Technologie lückenlos zu gewährleisten. Die Swisscom habe in ihrer Standortbegründung selbst ausgeführt, dass der vorliegende Ausbau einem ersten Schritt für den UMTS-Ausbau im Gebiet Uitikon, Waldegg und Birmensdorf entspreche. Müssten die durch den "idealen" Standort eingesparten weiteren Antennenanlagen später aus Kapazitätsgründen doch noch erstellt werden, so würde ein gewichtiger Vorteil des hier zu beurteilenden Standorts wegfallen.
Bei der nach Art. 24 RPG gebotenen Interessenabwägung sei zu berücksichtigen, dass Mobilfunkanlagen - eine zahlenmässig bedeutende Gruppe von Bauten und Anlagen ausserhalb der Bauzone - eine vergleichsweise geringe Lebensdauer aufweisen und relativ einfach auf- und abgebaut werden können. Die Verhältnisse änderten sich rasch und es kämen immer wieder neue Bedürfnisse hinzu, wie gerade der vorliegende Fall zeige. Ergeben sich im Rahmen dieser Entwicklungen insgesamt bessere Lösungen an anderen Standorten, so müsse bei Vorliegen eines genügend grossen Interesses auch die Verschiebung einer bestehenden, rechtskräftig bewilligten Anlage verlangt werden können. Vor diesem Hintergrund bestehe ein öffentliches Interesse an einer zeitlichen Beschränkung der Bewilligung für Mobilfunkanlagen ausserhalb der Bauzonen.
Das ARE beantragt, die Praxis in diesem Sinne zu präzisieren. Dementsprechend sei die streitige Bewilligung, sofern sie grundsätzlich bestätigt werde, mit einer Resolutivbedingung zu ergänzen, wonach die Bewilligung dahinfalle, wenn die Bewilligungsvoraussetzungen nicht mehr erfüllt seien, insbesondere wenn im Abdeckungsgebiet der bewilligten Anlage aus Kapazitätsgründen eine weitere Anlage notwendig werde.
3.4 Die Beschwerdegegnerinnen legen dar, dass nur ein Mast (Nr. 47) der Hochspannungsleitung innerhalb der Bauzone liege. Dieser sei aus radioplanerischer Sicht ungeeignet, weil der Leitungsmast nur 20 m vom Wald entfernt liege und durch diesen sowohl vom nordwestlich gelegenen Dorfzentrum von Uitikon als auch vom südöstlich gelegenen Dorfteil Waldegg abgeschirmt werde. Auch der tiefer gelegene Dorfteil "Sternenquartier" könnte nicht abgedeckt werden.
Die Beschwerdegegnerinnen beantragen, auf den Antrag des ARE zur Resolutivbedingung sei schon mangels Parteistellung des ARE nicht einzutreten. Eine solche Bedingung sei auch nicht nötig, weil die Mobilfunkbetreiberinnen schon konzessionsrechtlich verpflichtet seien, Antennenanlagen, die für den Netzzusammenhang nicht mehr benötigt würden, wieder abzubauen. Zudem bestehe die Möglichkeit, die streitbetroffene Baubewilligung zu widerrufen, falls die Bewilligungsvoraussetzungen weggefallen seien.
Nach Auffassung der Beschwerdegegnerinnen folgt aus der Eigentumsgarantie und der Wirtschaftsfreiheit grundsätzlich ein Anspruch auf eine unbefristete und unbedingte Baubewilligung; eine Resolutivbedingung bzw. ein Beseitigungsrevers dürfe nur aufgrund einer klaren gesetzlichen Grundlage angeordnet werden. Diese fehle hier; insbesondere genüge Art. 24 lit. b RPG nicht.
Die Beschwerdegegnerinnen bestreiten, dass sich Mobilfunkanlagen leicht auf- und abbauen liessen: Diese seien Teil eines überaus komplexen Mobilfunknetzes; erfahrungsgemäss sei mit einem durchschnittlichen Planungs- und Realisierungshorizont von rund 2 Jahren zu rechnen. Eine Mobilfunkanlage bestehe zum grössten Teil aus einer festen Infrastruktur (Fundament, Mast, Kabine, Klimaanlage, Stromversorgung, Kabelzuleitungen, etc.), die weitgehend unabhängig von der verwendeten Funktechnologie genutzt werden könne. Sie stelle daher eine langfristige Investition dar.
Zudem verkenne der Antrag des ARE, dass der Funknetzaufbau in zwei Schritten erfolge. Zunächst werde, mit einem sogenannten Makrostandort, die Initialversorgung sichergestellt (sog. "Coverage-Layer"). Genüge dieser aufgrund eines hohen funktechnischen Verkehrsaufkommens nicht, um eine konzessionskonforme Abdeckung sicherzustellen, würden in einem zweiten Schritt sogenannte Füllstandorte gebaut, welche die Kapazität im zu versorgenden Gebiet verbessern ("Kapazitäts-Layer"). Müsste aus Kapazitätsgründen ein zusätzlicher UMTS-Standort in der Gemeinde Uitikon errichtet werden (womit allerdings nicht zu rechnen sei), so würde dieser den Mobilfunknetzbetreiberinnen lediglich als "Füllstandort" dienen und könnte den Standort an der Langackerstrasse, der zum "Coverage-Layer" gehöre, nicht ersetzen.
Es wäre unverhältnismässig, wenn die Beschwerdegegnerinnen auf bestehende Makro-Standorte ausserhalb der Bauzone verzichten müssten, um einen zusätzlichen Standort innerhalb der Bauzone errichten zu können. In diesem Fall müssten sie ihr gesamtes Netzdesign neu planen und strukturieren. Dies wäre ein schwerer Eingriff in ihre Eigentums- und Wirtschaftsfreiheit.
Rund eine Drittel der Makro-Standorte der Swisscom liege ausserhalb der Bauzone, um auch weniger dicht besiedelte Gebiete und Verkehrsachsen versorgen zu können. Hiervon profitierten auch Polizei, Sanität, Feuerwehr und weitere Behörden. Indessen seien die Erstellungskosten solcher Makro-Standorte z.T. erheblich; sie beliefen sich durchschnittlich auf rund Fr. 325'000.--. Bei einer befristeten Bewilligungserteilung wäre der Investitionsschutz nicht mehr ausreichend gewährleistet. Die vom ARE beantragte Praxisänderung hätte deshalb zur Folge, dass die heute bestehende Flächenversorgung in vielen Fällen nicht mehr aufrechterhalten werden könne, insbesondere in weniger dicht besiedelten Gebieten und Randregionen.
4. Im Folgenden ist zunächst zu prüfen, ob das Verwaltungsgericht die Standortgebundenheit der Antennen zu Recht bejaht hat.
4.1 Antennen für den Mobilfunk können nach der Rechtsprechung ausnahmsweise auf einen Standort ausserhalb der Bauzonen angewiesen sein, wenn eine Deckungs- oder Kapazitätslücke aus funktechnischen Gründen mit einem oder mehreren Standorten innerhalb der Bauzonen nicht in genügender Weise beseitigt werden kann bzw. es bei einem Standort innerhalb der Bauzonen zu einer nicht vertretbaren Störung der in anderen Funkzellen des Netzes verwendeten Frequenzen kommen würde. Nicht ausreichend sind dagegen wirtschaftliche Vorteile des gewählten Standorts (z.B. geringere Landerwerbskosten; voraussichtlich geringere Zahl von Einsprachen) oder zivilrechtliche Gründe für die Standortwahl, wie z.B. die Weigerung von Eigentümern, einer Mobilfunkantenne auf ihren Grundstücken innerhalb der Bauzonen zuzustimmen (Urteile 1A.186/2002 vom 23. Mai 2003 E. 3.1, in: ZBl 105/2004 S. 103; RDAF 2005 I S. 591; 1A.120/2006 vom 12. Februar 2007 E. 3.1, in: URP 2007 S. 827; RDAF 2008 I S. 564).
4.2 In zwei jüngeren Entscheiden hat das Bundesgericht diese Rechtsprechung präzisiert für Mobilfunkanlagen, die auf bestehende Bauten und Anlagen, wie namentlich Hochspannungs- und Antennenmasten, montiert werden. Danach kann die Standortgebundenheit bei derartigen Standorten ausserhalb der Bauzonen auch dann bejaht werden, wenn diese zwar nicht aus funktechnischen Gründen unentbehrlich, sich aber im Rahmen einer konkreten Interessenabwägung als wesentlich geeigneter erweisen als mögliche Standorte innerhalb der Bauzone (Urteil 1C_345/2008 vom 29. Januar 2009 E. 2.3 und 2.5). Voraussetzung ist, dass die Mobilfunkanlage ausserhalb der Bauzonen keine erhebliche Zweckentfremdung von Nichtbauzonenland bewirkt und nicht störend in Erscheinung tritt. Dies ist grundsätzlich nur an Örtlichkeiten möglich, an denen sich bereits zonenkonforme oder zonenwidrige Bauten und Anlagen befinden (<ref-ruling> E. 4.3.3 S. 326 f.; 409 E. 4.2 S. 417 f.).
4.3 Wie sich aus den Standortbegründungen der Beschwerdegegnerinnen ergibt, verfügt die Sunrise bislang über keinen Standort mit UMTS in der Region; die UMTS-Versorgung der Gemeinde Uitikon Waldegg durch die Swisscom ist lückenhaft bzw. von sehr schlechter Qualität. Insofern besteht für beide Betreiber ein Bedürfnis für UMTS-Sendeanlagen.
Der umstrittene Standort weist, im Vergleich zu den untersuchten Alternativstandorten innerhalb und ausserhalb der Bauzone, den Vorteil auf, dass er fast das gesamte Gemeindegebiet flächendeckend versorgen kann, während bei allen anderen Standorten Versorgungslücken auftreten würden, die nur mittels zusätzlicher Antennenanlagen geschlossen werden könnten. Insbesondere scheidet auch der vom ARE favorisierte Standort auf dem bestehenden Hochspannungsleitungsmast in der Bauzone aus, wie die Beschwerdegegnerinnen überzeugend dargelegt haben. Insofern erscheint der in Aussicht genommene Standort wesentlich günstiger als andere Standorte.
4.4 Die Beschwerdeführer bestreiten dies nicht. Sie machen aber geltend, die Standortgebundenheit ausserhalb der Bauzone könne erst dann bejaht werden, wenn die Versorgung auch durch mehrere Antennenstandorte innerhalb der Bauzone nicht gewährleistet werden könne.
Zwar ist es richtig, dass eine Lösung mit einer einzigen neuen Antenne einer solchen mit zwei Antennen nicht in jedem Fall vorzuziehen ist, sofern Antennenstandorte an noch unüberbauten Orten ausserhalb der Bauzone beansprucht werden (vgl. Urteil 1C_228/2007 vom 28. November 2008 E. 5.5.3). Im vorliegenden Fall sollen die Antennen jedoch an einem bereits bestehenden Standort ausserhalb der Bauzone montiert werden, weshalb zu prüfen ist, ob die Standortgebundenheit nach der oben (E. 4.2) dargelegten neueren Rechtsprechung bejaht werden kann.
Die neuen Antennen sollen auf dem Dach einer bestehenden landwirtschaftlichen Baute errichtet werden, auf der sich bereits GSM-Mobilfunkantennen der Beschwerdegegnerinnen befinden. Diejenigen der Sunrise sind von einer kaminartigen Verschalung umgeben; diejenigen der Swisscom sind auf zwei ca. 3 m hohen Masten montiert, die den Dachfirst nur knapp überragen. Die Antennen treten somit relativ diskret in Erscheinung und wirken nicht störend; die dazugehörigen Geräte sind im Gebäudeinnern untergebracht.
Die bewilligte Erweiterung ändert nichts am aktuellen Erscheinungsbild der Scheune, werden doch lediglich die bisherigen GSM-Antennen durch GSM-/UMTS-Dualbandantennen ersetzt. Würde die beantragte Erweiterung nicht bewilligt, könnte der Standort in der aktuellen Konfiguration (nur GSM-Dienste) weiter betrieben werden und es müssten (zusätzlich) neue Standorte für UMTS gefunden werden. Es erscheint daher raumplanerisch sinnvoll, eine Konzentration aller Mobilfunk-Antennen an der bestehenden Anlage anzustreben.
4.5 Nach dem Gesagten durften die Behörden die Standortgebundenheit der Anlage i.S.v. Art. 24 lit. a RPG bejahen.
5. Zu prüfen ist weiter, ob einer unbedingten Erteilung der Ausnahmebewilligung überwiegende raumplanerische Interessen entgegenstehen (Art. 24 lit. b RPG), wie dies das ARE geltend macht.
5.1 Nachdem die Ausnahmebewilligung insgesamt angefochten wurde, kann das Bundesgericht diese ganz oder teilweise verweigern oder die Bewilligung unter zusätzlichen Auflagen oder Bedingungen erteilen. Davon gehen auch die Beschwerdegegnerinnen aus, wenn sie beantragen, das Bundesgericht möge sie mittels einer Auflage verpflichten, die streitbetroffene Mobilfunkanlage gemäss den im neuen Standortdatenblatt vom 15. September 2008 ausgewiesenen Parametern zu betreiben. Insofern kann das Bundesgericht auf Anregung des ARE prüfen, ob die Ausnahmebewilligung mit einer Nebenbestimmung versehen werden muss. Dabei steht dem Bundesgericht allerdings kein Ermessen zu, d.h. dieser Anregung kann nur gefolgt werden, wenn die Erteilung einer unbedingten Ausnahmebewilligung rechtswidrig wäre.
5.2 Das Anliegen des ARE ist verständlich: Die Bejahung der (relativen) Standortgebundenheit erfolgt aufgrund einer Interessenabwägung, gestützt auf die tatsächliche Situation im Zeitpunkt der Bewilligung. Verändern sich die Verhältnisse, beispielsweise durch die Errichtung zusätzlicher Mobilfunkanlagen innerhalb der Bauzone, so kann dies zur Folge haben, dass die Anlage nicht mehr ausserhalb der Bauzone bewilligt werden dürfte. Wurde die Ausnahmebewilligung ohne eine entsprechende Nebenbestimmung erteilt, bleibt sie jedoch bestandskräftig. Zwar ist der Widerruf einer ursprünglich fehlerfreien Verfügung aufgrund veränderter Verhältnisse möglich, wenn das Interesse an der richtigen Rechtsanwendung das Interesse am Vertrauensschutz und an der Rechtssicherheit überwiegt (<ref-ruling> E. 7a S. 313 f.; <ref-ruling> E. 3a S. 155; <ref-ruling> E. 4b S. 252 f,; HÄFELIN/MÜLLER/UHLMANN, Verwaltungsrecht, 5. Aufl., Rz. 1034). Dem Interesse am Vertrauensschutz wird jedoch regelmässig der Vorrang eingeräumt, wenn mit der Verfügung eine Befugnis eingeräumt wurde (wie z.B. bei der Baubewilligung), von der der Berechtigte bereits Gebrauch gemacht hat, sofern dies erhebliche Investitionen erforderte und zur Schaffung eines Zustands geführt hat, der nur unter Vernichtung gutgläubig geschaffener Werte wieder beseitigt werden kann (HÄFELIN/MÜLLER/UHLMANN, a.a.O. Rz. 1015; PETER HÄNNI, Planungs- Bau- und besonderes Umweltschutzrecht, 5. Aufl., S. 337 f.). Wird die Ausnahmebewilligung dagegen mit einer Resolutivbedingung erteilt, weiss der Berechtigte, dass ihm die Bewilligung nur bis zum Bedingungseintritt erteilt wird, und kann sich zu diesem Zeitpunkt nicht mehr auf Vertrauensschutzgesichtspunkte berufen.
Zwar besteht eine konzessionsrechtliche Verpflichtung, Antennenanlagen abzubauen, die für den Netzzusammenhang nicht mehr benötigt werden. Daraus folgt aber keine Verpflichtung der Mobilfunkbetreiber, auf rechtskräftig bewilligte und für den Netzaufbau verwendete Antennenanlagen ausserhalb der Bauzone zu verzichten, wenn deren Funktion von neueren Mobilfunk-Basisstationen innerhalb der Bauzone übernommen werden könnte.
5.3 Die Verbindung einer Bewilligung mit Auflagen und Bedingungen bedarf jedoch grundsätzlich einer gesetzlichen Grundlage, wobei es genügen kann, wenn sich die Zulässigkeit der Nebenbestimmung aus dem mit dem Gesetz verfolgten Zweck ergibt (HÄFELIN/MÜLLER, a.a.O. Rz. 918; HÄNNI, a.a.O., S. 335). Eine Bewilligung kann insbesondere mit einer Nebenbestimmung verbunden werden, wenn sie aufgrund der gesetzlichen Bestimmungen überhaupt verweigert werden könnte.
So erachtete das Bundesgericht einen Beseitigungsrevers für den Fall des Ausbaus der angrenzenden Strasse für zulässig, da die Baubewilligung wegen der in Aussicht genommenen Erweiterung der Strasse auch einstweilen hätte verweigert werden dürfen (<ref-ruling> E. 3 und 4a S. 485 f.). Im Urteil 1P.329/2005 vom 27. Juli 2005 (E. 3.5) war der Umbau einer Alphütte in ein Ferienhäuschen nach Art. 24d RPG bewilligt worden, unter der Bedingung, dass das Gebäude vom ersten Schneefall bis zur Ausaperung nicht bewohnt werden dürfe. Auch diese Bedingung hielt das Bundesgericht für zulässig, weil die Ausnahmebewilligung wegen der erheblichen Lawinengefährdung des Zugangs nach Art. 24d Abs. 3 lit. e RPG hätte verweigert werden können.
5.4 Die Anordnung einer Resolutivbedingung wäre somit zulässig und (als mildere Massnahme) möglicherweise geboten, wenn die Gesamtinteressenabwägung nach Art. 24 lit. b RPG ansonsten negativ ausfallen würde.
Das ARE macht geltend, dass es sich bei Mobilfunkanlagen um eine zahlenmässig bedeutende Gruppe von Bauten und Anlagen ausserhalb der Bauzone mit einer vergleichsweise geringen Lebensdauer handle, bei denen sich die Verhältnisse rasch änderten und immer wieder neue Bedürfnisse hinzukämen, weshalb ein öffentliches Interesse an einer zeitlichen Beschränkung der Bewilligung für Mobilfunkanlagen ausserhalb der Bauzonen bestehe.
Allerdings handelt es sich hierbei um ein generelles, nicht nur Mobilfunkanlagen betreffendes Problem: Es besteht ein öffentliches Interesse daran, Anlagen, die aufgrund veränderter Verhältnisse nicht mehr benötigt werden oder nicht mehr auf einen Standort ausserhalb der Bauzone angewiesen sind, zu beseitigen bzw. in die Bauzonen verlegen zu können.
Dieses Problem wird bei Mobilfunkanlagen durch die relativ kurze Lebensdauer der Sendeantennen entschärft: Müssen diese ersetzt oder ergänzt werden, bedarf es - wie der vorliegende Fall zeigt - regelmässig einer neuen Ausnahmebewilligung gemäss Art. 24 RPG, weshalb erneut geprüft werden kann und muss, ob die Anlage aufgrund der aktuellen Verhältnisse auf einen Standort ausserhalb der Bauzone angewiesen ist und ihr keine überwiegenden Interessen entgegenstehen. Dies ist zu verneinen, wenn raumplanungsrechtlich bessere Mobilfunkstandorte innerhalb oder ausserhalb der Bauzone vorhanden oder geplant sind.
Der Auffassung des ARE, dass die Interessenabwägung im vorliegenden Fall ohne Bedingung oder Befristung der Bewilligung negativ ausfallen würde, ist nicht zu folgen. Vielmehr liegen aktuell die Voraussetzungen für die Erteilung einer Ausnahmebewilligung vor. Die vorgeschlagene Resolutivbedingung stellt deshalb keine mildere Massnahme dar, sondern verschlechtert die Rechtsposition der Beschwerdegegnerinnen, indem sie ihnen den mit einer Baubewilligung üblicherweise verbundenen Vertrauens- und Bestandesschutz verweigert.
5.5 Nach dem Gesagten waren die kantonalen Behörden nicht gehalten, die Ausnahmebewilligung mit einer Resolutivbedingung zu erteilen.
6. Zu prüfen ist schliesslich, ob die Anlage die Anforderungen der Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) erfüllt. Die Antennen der Beschwerdegegnerinnen befinden sich auf einem Dach und bilden deshalb eine gemeinsame Anlage i.S.v. Ziff. 62 Abs. 1 Anhang 1 NISV. Sie müssen daher zusammen den massgeblichen Anlagegrenzwert von 5 V/m einhalten (Ziff. 64 lit. c Anhang 1 NISV).
6.1 Das BAFU hat in seiner Vernehmlassung verschiedene Widersprüche und Ungenauigkeiten des Standortdatenblatts und der Baupläne kritisiert. Diese waren von den Beschwerdeführern nicht beanstandet und von den kantonalen Behörden nicht bemerkt worden. Praxisgemäss werden jedoch derartige Einwände des BAFU noch im bundesgerichtlichen Verfahren berücksichtigt (vgl. Urteil 1A.118/2005 vom 12. Dezember 2005 E. 3, in: URP 2006 S. 180).
6.2 Die Beschwerdegegnerinnen haben die Kritik des BAFU anerkannt und ein neues Standortdatenblatt vom 15. September 2008 eingereicht. Darin wurden die vom BAFU beanstandeten Mängel behoben: Im Zusatzblatt 2 (Technische Angaben zu den Sendeantennen) wird klargestellt, dass die Funkdienste UMTS und GSM900 der Beschwerdegegnerin 1 durch einen einzigen Antennentyp (Dualband-Antenne Kathrein 742264) wahrgenommen werden sollen. Dies entspricht dem Baueingabeplan, wonach pro Senderichtung lediglich eine Antenne vorgesehen ist. OMEN Nr. 3 wurde neu im Situationsplan eingezeichnet und die Antennenbezeichnung in der dem Standortdatenblatt beigefügten Grundbuchplankopie berichtigt.
6.3 Die Immissionsberechnung des neuen Standortdatenblattes bestätigt, dass der Anlagegrenzwert an allen Orten mit empfindlicher Nutzung eingehalten wird; unter Berücksichtigung des neuen Antennentyps ergeben sich sogar etwas tiefere Immissionswerte als im ursprünglichen Standortdatenblatt. (4.61 V/m statt 4.84 V/m beim höchstbelasteten OMEN Nr. 3). Das BAFU hat in seiner Stellungnahme vom 20. Januar 2009 bestätigt, dass die Baubewilligung aus umweltrechtlicher Sicht erteilt werden könne.
6.4 Die Bau- bzw. Ausnahmebewilligung ist deshalb in dem Sinne zu modifizieren, dass die Anlage entsprechend den Parametern des neuen Standortdatenblatts zu errichten und zu betreiben ist.
7. Die Beschwerde ist danach teilweise gutzuheissen und im Übrigen abzuweisen. Die Beschwerdeführer unterliegen im Wesentlichen und tragen daher zwei Drittel der Gerichtskosten; ein Drittel ist den Beschwerdegegnerinnen aufzuerlegen (<ref-law>). Die Beschwerdeführer haben den Beschwerdegegnerinnen eine reduzierte Parteientschädigung zu zahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und die Bau- und Ausnahmebewilligung dahingehend abgeändert, dass die Anlage entsprechend den Parametern des Standortdatenblatts vom 15. September 2008 zu errichten und zu betreiben ist.
Im Übrigen wird die Beschwerde abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern zu 2/3 (Fr. 2'000.--) und den Beschwerdegegnerinnen zu insgesamt 1/3 (je Fr. 500.--, zusammen Fr. 1'000.--) auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerinnen für das bundesgerichtliche Verfahren mit je Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Gemeinde Uitikon, der Baudirektion, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, 3. Kammer, sowie den Bundesämtern für Umwelt und für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 25. Februar 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber