Sachverhalt: A. Der Gemeinderat Birmenstorf erteilte D._ am 3. Mai 1999 eine Baubewilligung für den Um- und Ausbau eines Weidestalls und für die teilweise Nutzungsänderung für Pferdehaltung auf der Parzelle Nr. 745 in der Landwirtschaftszone. Die Baubewilligung wurde für den Fall, dass eine Aufgabe oder eine starke Reduktion des Schaf- oder Pferdebestands bzw. die minimale Rauhfutterbasis von 5.26 ha landwirtschaftlichem Nutzland nicht mehr vorliegt, mit einem Beseitigungsrevers versehen. Nachdem im Jahr 2009 nicht bewilligte Veränderungen am Weidestall festgestellt wurden, reichte D._ ein nachträgliches Baugesuch ein, welches die Abteilung für Baubewilligungen des Departements Bau, Verkehr und Umwelt (BVU) am 29. Juli 2010 abwies und den Rückbau des Stalls anordnete. Die dagegen von D._ erhobenen Beschwerden wies der Regierungsrat des Kantons Aargau mit Beschluss vom 29. Juni 2011 und das Verwaltungsgericht des Kantons Aargau mit Entscheid vom 27. Februar 2012 ab. Dieser erwuchs unangefochten in Rechtskraft. Am 4. März 2013 reichte D._ beim Gemeinderat hinsichtlich der Rückbauverfügung ein Wiedererwägungsgesuch ein. Auf dieses trat das BVU nicht ein. Die dagegen erhobene Verwaltungsbeschwerde wies der Regierungsrat am 26. Februar 2014 ab, soweit er darauf eintrat. Diesen Entscheid focht D._ erfolglos beim Verwaltungsgericht sowie beim Bundesgericht (Urteil 1C_462/2015 vom 22. Februar 2016) an. B. Mit Eingabe vom 2. und 23. Dezember 2016 stellten A. und B. C._, Pächter der Parzelle Nr. 745, ein Baugesuch für den Um- und Anbau des Weidestalls. Auf das als Wiedererwägungsgesuch qualifizierte Baugesuch trat weder der Gemeinderat noch der Regierungsrat ein. Die dagegen von A. und B. C._, die im Frühjahr 2018 die Parzelle Nr. 745 erworben hatten, erhobene Beschwerde hiess das Verwaltungsgericht gut und wies die Sache an den Gemeinderat zurück. Zur Begründung verwies es auf die neuen Eigentumsverhältnisse an der Parzelle Nr. 745. Am 21. Januar 2019 wies der Gemeinderat das Wiedererwägungsgesuch ab. Dagegen erhoben A. und B. C._ Sprungbeschwerde an das Verwaltungsgericht, welches die Beschwerde am 22. August 2019 abwies. C. Mit Eingabe vom 27. September 2019 beantragen A. und B. C._, das Urteil des Verwaltungsgerichts sei vollumfänglich aufzuheben und es sei das vorliegende Verfahren vom Bundesgericht an die Vorinstanz zurückzuweisen zwecks Gutheissung ihres Wiedererwägungsgesuchs vom 2. bzw. 23. Dezember 2016. Weiter sei kein Abbruch des bestehenden Schaf- und Pferdestalls auf der Parzelle Nr. 745 vorzunehmen bzw. zu verfügen. Die Rückbauverfügung des Gemeinderates vom 9. August 2010 sei nicht zu vollstrecken. Das Verwaltungsgericht sowie das BVU beantragen, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Der Gemeinderat vertritt die Auffassung, die Stallbaute solle - soweit rechtlich und unter Nutzung der Ermessensspielräume möglich - für eine zonenkonforme landwirtschaftliche Nutzung weiterhin Bestand haben. Das Bundesamt für Raumentwicklung nahm Stellung, ohne einen konkreten Antrag zu stellen. Es wies aber darauf hin, dass den Beschwerdeführern keine weiteren Verzögerungen mehr zugestanden werden sollten. Die Beschwerdeführer halten an ihren Anträgen fest. D. Mit Präsidialverfügung vom 23. Oktober 2019 erkannte das Bundesgericht der Beschwerde die aufschiebende Wirkung zu.