Sachverhalt: A. Das Grundstück Nr. 487 (Grundbuch Gams) befindet sich in der Landwirtschaftszone der Gemeinde Gams. Es war ursprünglich mit einem Wohnhaus (Vers.-Nr. 946), einem Sticklokal (Vers.-Nr. 947) und einer freistehenden Scheune (Vers.-Nr. 945) überbaut. Das Sticklokal wurde 1973 mit dem Wohnhaus vereinigt. Ende der 70er Jahre erteilte die Gemeinde Gams dem damaligen Grundstückseigentümer zwei Bewilligungen für den Umbau des Wohnhauses (Vers.-Nr. 946), ohne die Zustimmung der zuständigen kantonalen Stelle einzuholen (Bewilligungen vom 18. Mai 1976 und vom 27. August 1979). Am 16. August 1980 bewilligte der Gemeinderat Gams, wiederum ohne die Zustimmung des Kantons, den Umbau der Scheune (Vers.-Nr. 945). Nach den Bauplänen waren im Erdgeschoss neben dem Keller ein Bügelraum, ein Waschraum und ein WC, im Obergeschoss eine Doppelgarage und ein Arbeitsraum sowie im Dachgeschoss ein durchgehender Abstellraum geplant. Die Scheune sollte über die Süd- und Ostfassade befenstert und neu unterfangen werden. Ausserdem sollte auf der Westseite eine Zufahrt zur Doppelgarage geschaffen werden. B. Am 7. Mai 1987 wurde das Grundstück Nr. 487 an die in Gams wohnhaften Eheleute X._ verkauft. Am 17. Februar 2004 reichte Herr X._ ein Baugesuch für die Erweiterung des Wohnzimmers unter Reduktion der Garage, den Einbau eines Specksteinofens und die Anpassung der Befensterung im Gebäude Vers.-Nr. 945 (ehemalige Scheune) ein. Auf Aufforderung des kantonalen Amts für Raumentwicklung (AREG) reichte die Gemeinde am 7. September 2005 alle früher erteilten Baubewilligungen sowie eine Bestandesaufnahme über den heutigen baulichen Zustand des Gebäudes Vers.-Nr. 945 ein. Danach sind im Erdgeschoss eine Sauna, ein Bad mit WC, ein separates WC und ein Abstellraum bzw. eine Waschküche vorhanden; im Obergeschoss befindet sich neben der Doppelgarage ein Wohn- und Essraum, und das Dachgeschoss wird als Schlafzimmer genutzt. Am 6. Oktober 2005 stellte das AREG der Gemeinde und Herr X._ einen Verfügungsentwurf zur Stellungnahme zu, weil es nicht nur beabsichtigte, die Zustimmung zum Bauvorhaben zu verweigern, sondern auch, die Gemeinde zum Rückbau der Wohnnutzung in der ehemaligen Scheune (Vers.-Nr. 945) aufzufordern. Am 4. November 2005 teilte der Rechtsvertreter von Herr X._ dem AREG mit, er teile die Auffassung, dass das Baugesuch nicht bewilligungsfähig sei und nachträglich auch keine Zustimmung zur Baubewilligung vom 16. August 1980 und den seither ohne Bewilligung vollzogenen Umbauten erteilt werden könne. Hingegen stünden der Schutz des guten Glaubens und der Verhältnismässigkeitsgrundsatz einer Wiederherstellung des rechtmässigen Zustands entgegen. C. Am 7. November 2005 verweigerte das AREG die Zustimmung zur Baubewilligung und die nachträgliche Zustimmung zur Umnutzung der Scheune Vers.-Nr. 945 in ein Wohnhaus und forderte die Gemeinde auf, innert 30 Tagen nach Rechtskraft die Wiederherstellung des rechtmässigen Zustands anzuordnen. Am 12. Dezember 2005 wies der Gemeinderat Gams das Baugesuch vom 17. Februar 2004 ab und eröffnete die Verfügung des AREG vom 7. November 2005. Nach Rücksprache mit dem AREG sah es vorerst vom Erlass einer Wiederherstellungsverfügung ab, um im Rahmen eines nachträglichen Baubewilligungsverfahrens zu klären, ob vom Gebäude Vers.-Nr. 946 her noch Erweiterungspotenzial bestehe, das für die Scheune Vers.-Nr. 945 genutzt und dort für die nachträgliche Bewilligung von Wohn-Nebenflächen eingesetzt werden könnte. Mit Verfügung vom 15. Februar 2007 erteilte das AREG die nachträgliche Zustimmung zu den Baubewilligungen des Gemeinderats vom 18. Mai 1976 und 27. August 1979 betreffend Umbau des Wohnhauses Vers.-Nr. 946. D. Am 11. Mai 2007 verfügte der Gemeinderat Gams, dass sämtliche nach dem 16. August 1980 vorgenommenen Änderungen zurückzubauen seien. Es sei folgender, von der Gemeinde bewilligter Bauzustand herzustellen: - UG: Keller, Bügelraum, Waschraum, WC - EG: Doppelgarage, Arbeitsraum - OG: Abstellraum Demnach seien namentlich folgende bauliche Änderungen vorzunehmen: - UG: Ausbau Sauna, Entfernen der elektrischen Leitungen im Sauna- raum - UG: Demontage Dusche mit Duschkabine Das Gebäude Vers.-Nr. 945 dürfe nicht für Wohnzwecke genutzt werden. Dies sei als öffentlich-rechtliche Eigentumsbeschränkung im Grundbuch anzumerken. Die künftige Nutzung des Nebengebäudes werde mit Stichproben überprüft. Zur Begründung führte der Gemeinderat aus, das AREG habe einen weitergehenden Rückbau verlangt, insbesondere die Reduktion der Belichtung im Dachgeschoss. Der Rückbau auf den Stand vor 1980 wäre jedoch unverhältnismässig, weil seit der Erteilung der Baubewilligung (ohne Zustimmung des Kantons) fast 27 Jahre zurückliegen und die Eheleute X._ das Grundstück in gutem Glauben erworben hätten. E. Gegen diese Verfügung haben die Eheleute X._ am 19. Juni 2007 Rekurs beim Baudepartement des Kantons St. Gallen erhoben, mit dem Begehren, auf eine Wiederherstellung sei vollständig zu verzichten und die Nutzung zu Wohnzwecken sei zu belassen. Das Baudepartement wies den Rekurs am 25. September 2008 ab, soweit es darauf eintrat. F. Gegen den Rekursentscheid gelangten die Eheleute X._ am 7. Oktober 2008 an das Verwaltungsgericht des Kantons St. Gallen. Dieses wies die Beschwerde am 9. Juli 2009 ab. G. Gegen den verwaltungsgerichtlichen Entscheid haben die Eheleute X._ am 14. September 2009 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und auf eine Wiederherstellung sei vollständig zu verzichten; die Nutzung zu Wohnzwecken sei zu belassen. H. Das Verwaltungsgericht und das Baudepartement des Kantons St. Gallen schliessen auf Abweisung der Beschwerde. Der Gemeinderat Gams hat auf eine Vernehmlassung verzichtet. I. Am 11. November 2009 bat der Rechtsvertreter der Beschwerdeführer um Einsicht in die kantonalen Akten. Mit Replik vom 17. Dezember 2009 machte er geltend, die Verfügung vom 12. Dezember 2005 sei nur dem früheren Rechtsvertreter der Beschwerdeführer, RA Y._, zugestellt und offenbar nicht an die Beschwerdeführer weitergeleitet worden. Diese Verfügung sei jedenfalls in Wiedererwägung zu ziehen, auch im Hinblick auf die mittlerweile über 30-jährige Nutzung als Wohnhaus. 