Sachverhalt: A. Am 20. Januar 2003 bewilligte der Gemeinderat Sarmenstorf X._, die bestehende Garage (Gebäude Nr. 901) auf der Parzelle Nr. 173 zu überdachen und einzuwanden. Dies sollte der Nutzung als Rüst- und Stauraum für die Aufbereitung, Lagerung und Trocknung von Blumen dienen. Das Grundstück liegt in der Landwirtschaftszone. B. Bei der Realisierung des Vorhabens wich der Bauherr von der Baubewilligung ab und erstellte eine Wendeltreppe anstelle einer geraden Treppe sowie zusätzlich einen Balkon. Für diese Bauten reichte X._ ein nachträgliches Baugesuch ein, gegen welches keine Einsprachen erhoben wurden. C. Nachdem das nachträgliche Baugesuch dem Departement Bau, Verkehr und Umwelt (BVU; Koordinationsstelle Baugesuche, heute: Abteilung für Baubewilligungen) zur Prüfung überwiesen worden war, führte dieses einen Augenschein durch und hielt am 19. Mai 2005 fest, die Projektänderungen entspreche den Anforderungen nach Art. 22 und 16a Abs. 2 RPG in Verbindung mit Art. 34 Abs. 2 und 4 RPV nur, wenn zweifelsfrei feststehe, dass die Blumenproduktion auch tatsächlich umgesetzt werde, ansonsten fehle die Betriebsnotwendigkeit. Das BVU räumte dem Gesuchsteller die Möglichkeit ein, bis Ende 2006 den bewilligten Rüstraum fertig zu stellen und nach Aufnahme der Blumenproduktion in Betrieb zu nehmen. Anschliessend seien die abgeschlossenen Abnahmeverträge vorzulegen und eine ergänzende Begründung für das Geländer nachzureichen. Bis zu diesem Zeitpunkt werde das Gesuch sistiert. Am Balkonanbau dürften bis dahin keine weiteren Arbeiten vorgenommen werden. D. Nachdem X._ am 20. April 2007 ergänzende Unterlagen zum Nachweis der Betriebsnotwendigkeit eingereicht hatte, stimmte die Abteilung für Baubewilligungen des BVU dem Baugesuch für die Wendeltreppe am 10. Juli 2007 unter Auflagen zu. Gleichzeitig wies sie das Baugesuch für den Balkon ab. Gestützt darauf bewilligte der Gemeinderat von Sarmenstorf mit Beschluss vom 20. August 2007 nur die Wendeltreppe und wies das Gesuch für den Balkonbau ab. Er wies den Bauherrn an, den Balkon innerhalb von drei Monaten nach Rechtskraft des Entscheids zu beseitigen. E. Eine Verwaltungsbeschwerde von X._ (vertreten durch seinen Sohn Y._) wies der Regierungsrat des Kantons Aargau am 22. Oktober 2008 ab. Auch das in der Folge angerufene kantonale Verwaltungsgericht wies die Beschwerde von X._ (als Grundeigentümer) und Y._ (als Pächter und Leiter des Betriebs) mit Urteil vom 21. Dezember 2009 ab. Es verneinte die Betriebsnotwendigkeit des Balkons. F. X._ und Y._ erheben am 19. Februar 2010 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und beantragen die Aufhebung des vorerwähnten Urteils. Sie machen eine Verletzung von Art. 34 Abs. 2 RPV, der Wirtschaftsfreiheit, des Verhältnismässigkeitsprinzips, des Willkürverbots und des rechtlichen Gehörs geltend. Gleichzeitig ersuchen sie um Gewährung der aufschiebenden Wirkung. Der Gemeinderat Sarmenstorf wie auch der Regierungsrat des Kantons Aargau schliessen auf Abweisung der Beschwerde, während das Verwaltungsgericht von der Möglichkeit zur Vernehmlassung keinen Gebrauch macht. Auch das Bundesamt für Raumentwicklung (ARE) verzichtet auf eine Stellungnahme. Mit Verfügung vom 29. März 2010 hat der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt. Im Rahmen des zweiten Schriftenwechsels halten die Beschwerdeführer sinngemäss an ihren Anträgen fest.