Sachverhalt: A. Z._ betreibt in Buchs einen gemischtwirtschaftlichen Landwirtschaftsbetrieb mit Milchwirtschaft, Rindermast sowie Acker- und Futterbau, den er 2006 von seinem Vater, D._, übernommen hat. Er bewirtschaftet 21.38 ha Eigenland und 16.11 ha Pachtland. Er hält 22 Milchkühe, 14 Stücke Aufzuchtvieh und 27 Stück Mastvieh, d.h. insgesamt 34.68 Grossvieheinheiten, und benötigt 2.467 Standardarbeitskräfte. Die bestehenden Ökonomiegebäude (mit Rinderstall, Milchvieh-Anbindestall, Heustock und Abladetenn) befinden sich nördlich der Krähstelstrasse und sind an das Restaurant Bergwerk angebaut. Dieses wird von der Schwester von D._ bewirtschaftet. Zur Entflechtung der beiden Betriebsteile wurde 1997 ein Betriebsleiterwohnhaus mit Stöckli südlich der Krähstelstrasse erstellt (Krähstelstrasse 30 und 32). Dort befindet sich auch eine Remise mit Garage. B. Z._ möchte seinen Betrieb durch Erhöhung der Zahl der Milchkühe auf 68 Stück vergrössern und hierfür einen neuen Milchvieh-Laufstall (23.5 m x 38.75 m) mit angebauter Bergehalle (18.94 m x 20 m; maximale Höhe 10 m ab dem gewachsenen und 11.50 ab dem projektierten Terrain), drei je 16 m hohe Hochsilos und eine unterirdische Jauchegrube (Volumen 830 m3) südlich der Krähstelstrasse und westlich seines Wohnhauses erstellen. Der Bauvorstand von Buchs erteilte hierfür am 21. Mai 2007 unter verschiedenen Auflagen die notwendige Baubewilligung und eröffnete dabei auch eine raumplanungsrechtliche Bewilligung der Baudirektion vom 30. März 2007. C. Gegen diese Beschlüsse wandten sich die Ehegatten A._, B._ und C._ als Nachbarn. Die Baurekurskommission I des Kantons Zürich wies den Rekurs am 29. Februar 2008 nach Durchführung eines Augenscheins ab. D. Die unterlegenen Nachbarn erhoben am 4. April 2008 Beschwerde gegen den Rekursentscheid an das Verwaltungsgericht des Kantons Zürich. Dieses wies die Beschwerde am 23. Oktober 2008 ab. E. Dagegen erhoben die Ehegatten A._, B._ und C._ am 10. Dezember 2008 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht. Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Baubehörden seien einzuladen, die nachgesuchte Baubewilligung für den Neubau eines Stalles und einer Bergehalle sei zu verweigern. Eventualiter sei die Angelegenheit zur ergänzenden Abklärung des Sachverhalts zurückzuweisen. F. Z._ (im Folgenden: der Beschwerdegegner) und die kantonale Baudirektion schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht und der Bauvorstand der Gemeinde Buchs beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das ARE macht in seiner Vernehmlassung vom 26. Februar 2009 punktuelle Bemerkungen zur Beschwerde und zum angefochtenen Entscheid, ohne einen Antrag zu stellen. Den Parteien wurde Gelegenheit gegeben, sich zur Vernehmlassung des ARE und den Eingaben der Gegenseite zu äussern. G. Mit Verfügung vom 8. Januar 2009 wurde das Gesuch um aufschiebende Wirkung abgewiesen.