Sachverhalt: A. Der EWZ-Hochspannungsleitungsmast Nr. 75 steht auf dem in der Landwirtschaftszone gelegenen Grundstück Kat.-Nr. 6749 an der Eichholzstrasse in Esslingen. Auf diesem Masten befindet sich bereits eine POLYCOM-Antennenanlage der Kantonspolizei Zürich und eine GSM/ UMTS-Basisstation der Orange Communications AG. Geplant ist eine zusätzliche Basisstation der Swisscom (Schweiz) AG, bestehend aus zwei Dualband-Antennen GSM900/UMTS mit einer Gesamtleistung von maximal 7'600 WERP und einer Richtfunkantenne. B. Am 21. Januar 2008 erteilte die Baudirektion des Kantons Zürich hierfür die Ausnahmebewilligung nach Art. 24 des Raumplanungsgesetzes (RPG; SR 700) unter Bedingungen und Auflagen. Der Gemeinderat Egg verweigerte am 25. Februar 2008 die Erteilung der Baubewilligung. Am 16. Dezember 2009 hiess die Baurekurskommission den dagegen gerichteten Rekurs der Swisscom (Schweiz) AG gut und wies die Sache zur Fortsetzung des Bewilligungsverfahrens an die kommunale Baubehörde zurück. Daraufhin erteilte der Gemeinderat Egg am 17. Mai 2010 die Baubewilligung und eröffnete sie zusammen mit der Ausnahmebewilligung der Baudirektion. C. Gegen die Ausnahmebewilligung und die Baubewilligung rekurrierten insgesamt 41 Parteien an die Baurekurskommission des Kantons Zürich (heute: Baurekursgericht). Diese wies die Rekurse am 1. Juni 2011 ab, soweit sie darauf eintrat. Dagegen gelangten 17 Parteien mit Beschwerde an das Verwaltungsgericht des Kantons Zürich. Dieses wies die Beschwerden am 24. November 2011 ab. D. Gegen den verwaltungsgerichtlichen Entscheid haben die im Rubrum genannten Personen am 17. Januar 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten und subsidiäre Verfassungsbeschwerde an das Bundesgericht erhoben. Sie beantragen im Wesentlichen, der angefochtene Entscheid, Ziff. IIb, III und IV des Entscheids der Baurekurskommission sowie die erstinstanzlichen Entscheide des Gemeinderats Egg und der Baudirektion seien aufzuheben; eventualiter sei die Sache zur weiteren Abklärung des Sachverhalts an die Vorinstanz zurückzuweisen. In verfahrensrechtlicher Hinsicht beantragen sie die Gewährung der aufschiebenden Wirkung, die Beschwerdeergänzung nach Zustellung aller relevanten Akten sowie die Durchführung eines zweiten Schriftenwechsels, eines Augenscheins und einer mündlichen öffentlichen Verhandlung. E. Die Swisscom (Schweiz) AG (im Folgenden: die Beschwerdegegnerin) beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen und der angefochtene Entscheid zu bestätigen. Die Baudirektion schliesst auf Abweisung der Beschwerde. Die Gemeinde Egg und das Bundesamt für Raumentwicklung (ARE) haben auf eine Vernehmlassung verzichtet. Das Bundesamt für Umwelt (BAFU) kommt in seiner Vernehmlassung zum Ergebnis, dass die von den Beschwerdeführer vorgebrachten Studien keinen Anlass zu einer Anpassung der Grenzwerte der Verordnung über den Schutz vor nichtionisierender Strahlung (NISV, SR 814.710) geben. F. In ihrer Replik vom 4. Mai 2012 erneuern die Beschwerdeführer ihre Anträge auf Beschwerdeergänzung und auf einen zweiten Schriftenwechsel nach Zustellung der eingereichten Akten. Mit Schreiben vom 9. Mai 2012 wurde ihnen mitgeteilt, dass die übrigen Verfahrensbeteiligten keine neuen Aktenstücke eingereicht haben. G. Mit Verfügung vom 23. Februar 2012 wurde der Beschwerde die aufschiebende Wirkung in dem Sinne zuerkannt, dass die neuen Mobilfunkantennen während der Hängigkeit des bundesgerichtlichen Verfahrens zwar auf Risiko der Beschwerdegegnerin erstellt, nicht aber in Betrieb genommen werden dürfen.