Sachverhalt: A. Der Gemeinderat Herznach bewilligte am 21. November 2002 das von X._ und Y._ am 15. Oktober 2002 eingereichte Baugesuch für einen Pferdestall auf der Parzelle Nr. 27 in der Gemeinde Herznach. X._ und Y._ realisierten dieses Projekt nicht und reichten ein überarbeitetes Baugesuch ein, welches der Gemeinderat Herznach mit Protokollauszug vom 16. Dezember 2004 bewilligte. Mit Verfügung vom 15. Dezember 2005 bewilligte der Gemeinderat ein weiteres, nochmals überarbeitetes Baugesuch für einen Pferdestall auf der Parzelle Nr. 27. B. Nachdem X._ und Y._ das Bauvorhaben entsprechend der Baubewilligung vom 15. Dezember 2005 realisiert hatten, stellte der Gemeinderat Herznach fest, dass ein Teil des Pferdestalls in der Landwirtschaftszone liegt. Mit Beschluss vom 8. Mai 2007 überwies er deshalb die Akten an das Departement Bau, Verkehr und Umwelt des Kantons Aargau, Abteilung für Baubewilligungen, zur Stellungnahme. Am 4. Juni 2007 wies dieses das Baugesuch ab. In Ziffer 2 verfügte das Departement Bau, Verkehr und Umwelt den Aufschub der Beseitigung bis Ende 2009. Mit Beschluss vom 14. Juni 2007 eröffnete der Gemeinderat Herznach X._ und Y._ diesen Entscheid. Gegen diesen Beschluss erhoben X._ und Y._ beim Regierungsrat des Kantons Aargau Beschwerde. Der Regierungsrat entschied am 17. September 2008, dass die Beschwerde abgewiesen werde. Ziffer 2 der Verfügung des Departements Bau, Verkehr und Umwelt werde aufgehoben und wie folgt neu formuliert: "2. Falls eine (teilweise) Einzonung der Parzelle Nr. 27 in der eingeleiteten Gesamtrevision nicht zustande kommt, ist der Pferdestall innert einer Frist von 3 Monaten ab Rechtskraft der Nichteinzonung in den rechtmässigen Zustand zu überführen respektive (teilweise) abzubrechen. Die Frist zur Wiederherstellung des gesetzmässigen Zustands beginnt ebenfalls zu laufen, wenn der Gemeinderat den Entscheid fällt, die eingeleitete Gesamtrevision nicht weiter zu verfolgen." Hierauf gelangten X._ und Y._ an das Verwaltungsgericht des Kantons Aargau, welches in teilweiser Gutheissung der Beschwerde den Entscheid des Regierungsrates im Kostenpunkt aufhob und die Kosten des Verfahrens vor dem Regierungsrat neu verteilte. Im Übrigen wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat. C. Mit Eingabe vom 14. September 2009 erheben X._ und Y._ Beschwerde beim Bundesgericht. Sie stellen den Antrag, das Urteil des Verwaltungsgerichts vom 17. Juni 2009 sei aufzuheben. Auf die Beseitigung des in die Landwirtschaftszone ragenden Teils des Pferdestalls sei zu verzichten. Eventualiter sei festzustellen, dass die Beschwerdeführer bei der Erstellung der Baute gutgläubig gehandelt hätten und die Voraussetzungen für den Schutz des Vertrauens erfüllt seien. Ungeachtet des Ausgangs dieses Verfahrens seien die Kosten dieses Verfahrens und die Prozesskosten der vorinstanzlichen Verfahren der Vorinstanz aufzuerlegen. D. Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen. Die Gemeinde Herznach verzichtet auf eine ergänzende Stellungnahme und verweist auf die Vorakten. Das Departement Bau, Verkehr und Umwelt des Kantons Aargau liess sich nicht vernehmen. Das Bundesamt für Raumentwicklung führt aus, die Beschwerde werfe aus Sicht des Bundesamtes keine grundsätzlichen planerischen oder planungsrechtlichen Fragen auf, welche eine Stellungnahme als notwendig erscheinen liessen. In ihrer Replik halten die Beschwerdeführer an ihren Anträgen fest.